Efficient algorithms for finding maximum matching in graphs
- 1 March 1986
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 18 (1), 23-38
- https://doi.org/10.1145/6462.6502
Abstract
This paper surveys the techniques used for designing the most efficient algorithms for finding a maximum cardinality or weighted matching in (general or bipartite) graphs. It also lists some open problems concerning possible improvements in existing algorithms and the existence of fast parallel algorithms for these problems.Keywords
This publication has 27 references indexed in Scilit:
- Heuristic matching for graphs satisfying the triangle inequalityJournal of Algorithms, 1984
- An analysis of alternative strategies for implementing matching algorithmsNetworks, 1983
- A shortest augmenting path method for solving minimal perfect matching problemsNetworks, 1981
- Sensitivity analysis of optimal matchingsNetworks, 1981
- An algorithm to solve the m × n assignment problem in expected time O(mn log n)Networks, 1980
- Finding optimum branchingsNetworks, 1977
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- An algorithm for a minimum cover of a graphProceedings of the American Mathematical Society, 1959
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956