A parametric study of matchings and coverings in weighted graphs
Given a weighted graph, a matching is a subset of the edges such that no two edges of the subset are incident to the same vertex. A covering is a subset of the edges such that each vertex is incident to at least one edge of the subset. Two problems are to find a maximum weight matching and minimum weight covering. Edmonds has developed an algorithm of algebraic growth to find a maximum matching. A review of this method is presented. A new algorithm for the solution of the minimum covering problem is developed. Under certain conditions, Lagrange multiplier methods can be applied to discrete programming problems. This is called the parametric approach, and is used here to find maximum matchings, subject to the condition that the number of edges in the solution is some fixed number, k. A study of methods for this 'k-cardinality' problem indicates several improvements in Edmonds' matching algorithm. The parametric technique is extended to solve the minimum k-cardinality covering problem. This algorithm is shown to be a generalization of Kruskal's algorithm for a minimum spanning tree. This leads to a discussion of matroid systems and greedy algorithms, and their relationship to the parametric approach. Matchings and coverings in weighted graphs have applications in resource allocation, diagnostics, and large scale system design.
What people are saying - Write a review
We haven't found any reviews in the usual places.
A PARAMETRIC APPROACH AND MAXIMUM MATCHING
5 other sections not shown
alternating path alternating tree Bipartite Graph blossom structure Cardinality Matching Algorithm constraints convex polyhedron cost plane covered nodes covering in G Define Direct Algorithm dual variable edge set edge weights Edmonds endpoints enters subgraph exposed node graph G greedy algorithm growth Hungarian tree incidence matrix incident inner vertex integer k-Cardinality Matching Curve k-cardinality matching problem Lagrange multiplier linear independence matching and covering matching in G matroid maximal independent set maximum cardinality matching maximum matching algorithm maximum matching problem minimum covering algorithm minimum k-cardinality covering minimum spanning tree minimum weight monotonic nonincreasing negative edges noninteger number of edges number of nodes odd cycles odd vertex sets orthogonality conditions outer node outer vertex outermost blossoms polyhedron edge polyhedron vertex root satisfied shown in Figure star subgraph strong augmenting path subgraph G subset TRANSFER transmitter vector Venn Diagram vertex weights vertices weak augmenting path weighted graph