Maximum Matching on Regular Nonbipartite Graphs

Varsha Dani, Thomas P. Hayes, Seth Pettie

Blocking flow-type maximum matching algorithms are based on finding maximal sets of shortest augmenting paths. They run in $O(m\sqrt{n})$ time, on both bipartite [HK73, Din70, Kar7…