An o(n2.5) Algorithm: For Maximum Matchings in General Graphs

HTML  XML Download Download as PDF (Size: 569KB)  PP. 1773-1782  
DOI: 10.4236/jamp.2018.69152    1,032 Downloads   3,192 Views  Citations
Author(s)

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.

Share and Cite:

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.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.