DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2017.10

Extending Search Phases in the Micali-Vazirani Algorithm

Authors: Michael Huang and Clifford Stein

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract

The Micali-Vazirani algorithm is an augmenting path algorithm that offers the best theoretical runtime of O(n^{0.5} m) for solving the maximum cardinality matching problem for non-bipartite graphs. This paper builds upon the algorithm by focusing on the bottleneck caused by its search phase structure and proposes a new implementation that improves efficiency by extending the search phases in order to find more augmenting paths. Experiments on different types of randomly generated and real world graphs demonstrate this new implementation's effectiveness and limitations.

Cite as

Michael Huang and Clifford Stein. Extending Search Phases in the Micali-Vazirani Algorithm. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.SEA.2017.10,
  author =	{Huang, Michael and Stein, Clifford},
  title =	{{Extending Search Phases in the Micali-Vazirani Algorithm}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.10},
  URN =		{urn:nbn:de:0030-drops-76141},
  doi =		{10.4230/LIPIcs.SEA.2017.10},
  annote =	{Keywords: matching, graph algorithm, experimental evaluation, non-bipartite}
}

Search Results

Documents authored by Huang, Michael

Extending Search Phases in the Micali-Vazirani Algorithm

Abstract

Cite as

Thanks for your feedback!

Could not send message