Efficient algorithms for finding maximum matching in graphs
Zvi Galil · ACM Computing Surveys · 1986
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.
Cited by 461 works. doi:10.1145/6462.6502 Open-access PDF
Authors
References
- The Art of Computer Programming
- The Design and Analysis of Computer Algorithms
- A note on two problems in connexion with graphs
- The Hungarian method for the assignment problem
- Combinatorial optimization: networks and matroids
- Combinatorial Optimization: Algorithms and Complexity.
- Maximal Flow Through a Network
- Sorting and Searching
- Paths, Trees, and Flowers
- Maximal Flow Through a Network