DEGREE CONSTRAINED SUBGRAPHS OF LINEAR GRAPHS.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1969
- Accession Number
- AD0692221
Entities
People
- Robert J. Urquhart
Organizations
- University of Michigan