Back
 JAMP  Vol.6 No.9 , September 2018
An o(n2.5) Algorithm: For Maximum Matchings in General Graphs
Abstract:
This article extend the John E. Hopcroft and Richart M. Karp Algorithm (HK Algorithm) for maximum matchings in bipartite graphs to the non-bipartite case by providing a new approach to deal with the blossom in alternating paths in the process of searching for augmenting paths, which different from well-known “shrinking” way of Edmonds and makes the algorithm for maximum matchings in general graphs more simple.
Cite this paper: Xie, Y. (2018) An o(n2.5) Algorithm: For Maximum Matchings in General Graphs. Journal of Applied Mathematics and Physics, 6, 1773-1782. doi: 10.4236/jamp.2018.69152.
References

[1]   Berge, C. (1957) Two Theorems in Graph Theory. Proceedings of the National Academy of Sciences of the USA, 43, 449-844. https://doi.org/10.1073/pnas.43.9.842

[2]   Balinski, M.L. (1969) Labelling to Obtain a Maximum Matching, in Combinatorial Mathematics and Its Applications. In: Bose, R.C. and Dowling, T.A., Eds., University of North Carolina Press, Chapel Hill, 585-602.

[3]   Witzgall, C. and Zahn Jr., C.T. (1965) Modification of Edmond’s Maximum Matching Algorithm. Journal of Research of the National Bureau of Standards, 69B, 91-98.

[4]   Edmonds, J. (1965) Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17, 449-467. https://doi.org/10.4153/CJM-1965-045-4

[5]   Hopcroft, J. and Karp, R.M. (1973) An n5/2 Algorithm for Maximum Matching in Bipartite Graphs. SIAM Journal on Computing, 225-231. https://doi.org/10.1137/0202019

[6]   Micali, S. and Vazirani, V.V. (1980) An Algorithm for Finding Maximum Matching in General Graphs. IEEE Annual Symposium on Foundations of Computer Science.

[7]   Peterson, P.A. and Lout, M.C. (1988) The General Matching Algorithm of Micali and Vazirani. Algorithmica, 511-533. https://doi.org/10.1007/BF01762129

 
 
Top