An O (N2.5) algorithm for maximum matching in general graphs
- 1 October 1975
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 100-112
- https://doi.org/10.1109/sfcs.1975.5
Abstract
This work presents a new efficient algorithm for finding a maximum matching in an arbitrary graph. Two implementations are suggested, the complexity of the first is O(n2.5) and the complexity of the second is O(m√n·log n) where n, m are the numbers of the vertices and the edges in the graph.Keywords
This publication has 3 references indexed in Scilit:
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973
- Modification of Edmonds' maximum matching algorithmJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965
- Paths, Trees, and FlowersCanadian Journal of Mathematics, 1965