Abstract
An algorithm for finding an optimum weight perfect matching in a graph is described. It differs from Edmonds’ “blossom” algorithm in that a perfect matching is at hand throughout the algorithm, and a feasible solution to the dual problem is obtained only at termination. In many other respects, including its efficiency, it is similar to the blossom algorithm. Some advantages of this “primal” algorithm for certain post-optimality problems are described. The algorithm is used to prove that, if the weights are integers, then the dual problem has an optimal solution which is integer-valued. Finally, some graph-theoretic results on perfect matchings are derived.
Research was done while this author was with the Department of Mathematical Sciences, Johns Hopkins University, and was supported in part by National Science Foundation Grant MCS76-08803.
Preview
Unable to display preview. Download preview PDF.
References
M.L. Balinski, “Establishing the matching polytope”, Journal of Combinatorial Theory B 13 (1972) 1–13.
M.L. Balinski and R.E. Gomory, “A primal method for the assignment and transportation problems”, Management Science 10 (1964) 578–593.
R.S. Barr, F. Glover and D. Klingman, “The alternating basis algorithm for assignment problems”, Mathematical Programming 13 (1977) 1–13.
N. Christofides, “Worst-case analysis of a new heuristic for the traveling salesman problem”, GSIA, Carnegie-Mellon University (1976).
W.H. Cunningham, “A network simplex method”, Mathematical Programming 11 (1976) 105–116.
J. Edmonds, “Paths, trees, and flowers”, Canadian Journal of Mathematics 17 (1965) 449–467.
J. Edmonds, “Maximum matching and a polyhedron with(0,1) vertices”, Journal of Research of the National Bureau of Standards 69B (1965) 125–130.
J. Edmonds, “An introduction to matching”, Lecture notes, Univ. of Michigan Summer Engineering Conf. (1967).
J. Edmonds and E.L. Johnson, “Matching: a well-solved class of integer linear programs”, in: R.K. Guy, et al., eds., Combinatorial structures and their applications (Gordon and Breach, New York, 1970).
J. Edmonds and E.L. Johnson, “Matching, Euler tours, and the Chinese postman”, Mathematical Programming 5 (1973) 88–124.
J. Edmonds, E.L. Johnson and S.C. Lockhart, “Blossom I, A computer code for the matching problem”, to appear.
J. Edmonds and W.R. Pulleyblank, Optimum matching (Johns Hopkins Press) to appear.
M. Hall, “Distinct representatives of subsets”, Bulletin of the American Mathematical Society 54 (1948) 922–926.
A.J. Hoffman and R. Oppenheim, “Local unimodularity in the matching polytope”, Annals of Discrete Mathematics 2 (1978) 201–209.
H.W. Kuhn, “The Hungarian method for the assignment problem”, Naval Research Logistics Quarterly 2 (1955) 83–97.
E.L. Lawler, Combinatorial optimization (Holt-Rinehart-Winston, New York, 1976).
L. Lovász, “On the structure of factorizable graphs”, Acta Mathematica Academiae Scientiarum Hungaricae 23 (1972) 179–195.
W.R. Pulleyblank, Faces of matching polyhedra, Thesis, University of Waterloo (1973).
W.R. Pulleyblank, “Dual integrality in b-matching problems”, CORE Discussion Paper, Louvain (1977).
W.R. Pulleyblank and J. Edmonds, “Facets of 1-matching polyhedra”, in: C. Berge and D. Ray-Chaudhuri, eds., Hypergraph seminar, Lecture Notes in Mathematics, No. 411 (Springer, Berlin, 1974).
A. Schrijver and P.D. Seymour, “A proof of total dual integrality of matching polyhedra”, Mathematical Centre, Amsterdam (1977).
P. Seymour, “On the 1-factors of regular graphs”, to appear.
J. Zaks, “On the 1-factors of n-connected graphs”, in: R.K. Guy et al., eds. Combinatorial structures and their applications (Gordon and Breach, New York, 1970).
Author information
Authors and Affiliations
Editor information
Additional information
Dedicated to the memory of D. Ray Fulkerson
Rights and permissions
Copyright information
© 1978 The Mathematical Programming Society
About this chapter
Cite this chapter
Cunningham, W.H., Marsh, A.B. (1978). A primal algorithm for optimum matching. In: Balinski, M.L., Hoffman, A.J. (eds) Polyhedral Combinatorics. Mathematical Programming Studies, vol 8. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0121194
Download citation
DOI: https://doi.org/10.1007/BFb0121194
Received:
Revised:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00789-7
Online ISBN: 978-3-642-00790-3
eBook Packages: Springer Book Archive