License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.10
URN: urn:nbn:de:0030-drops-76141
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7614/
Go to the corresponding LIPIcs Volume Portal


Huang, Michael ; Stein, Clifford

Extending Search Phases in the Micali-Vazirani Algorithm

pdf-format:
LIPIcs-SEA-2017-10.pdf (2 MB)


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.

BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs:2017:7614,
  author =	{Michael Huang and Clifford Stein},
  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 =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7614},
  URN =		{urn:nbn:de:0030-drops-76141},
  doi =		{10.4230/LIPIcs.SEA.2017.10},
  annote =	{Keywords: matching, graph algorithm, experimental evaluation, non-bipartite}
}

Keywords: matching, graph algorithm, experimental evaluation, non-bipartite
Seminar: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 03.08.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI