TITLE:
An o(n2.5) Algorithm: For Maximum Matchings in General Graphs
AUTHORS:
Yingtai Xie
KEYWORDS:
Matching, Augmenting Path, Blossom, Equivalent Digraph
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.6 No.9,
September
7,
2018
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.