Accession Number : AD0692221

Title :   DEGREE CONSTRAINED SUBGRAPHS OF LINEAR GRAPHS.

Descriptive Note : Technical rept. Jan 66-May 67,

Corporate Author : MICHIGAN UNIV ANN ARBOR SYSTEMS ENGINEERING LAB

Personal Author(s) : Urquhart,Robert J.

Report Date : JUL 1969

Pagination or Media Count : 164

Abstract : Given a weighted, undirected graph, a class of combinatorial problems is to find an optimum weighted subgraph, subject to certain degree constraints on the vertices of the subgraph. If the graph is bipartite, problems of this sort are equivalent to the classical transportation and assignment problems of operations research. When the graph is not bipartite, but the degree constraints are unity for all vertices, the problem is that of graphical matching or covering. The matching problem has been solved by Edmonds. The most general problem solved in this thesis is the 'degree constrained subgraph problem', in which each vertex has a separate upper and lower degree constraint. The factors problem is a special case, where the upper and lower constraints are equal at each vertex. Efficient algorithms for these cases have not previously appeared in the literature. The approach taken to solve these problems is characterized by the use of linear programming theory, both to motivate the algorithm, and to demonstrate the optimality of a solution. The work is shown to be applicable to large scale system design, parallel processing, scheduling, and selection of optimum routings. (Author)

Descriptors :   (*GRAPHICS, *COMBINATORIAL ANALYSIS), (*LINEAR PROGRAMMING, PROBLEM SOLVING), MATHEMATICAL MODELS, SYSTEMS ENGINEERING, CONVEX SETS, COMPUTER PROGRAMS, SCHEDULING, THESES

Subject Categories : Theoretical Mathematics
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE