License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.76
URN: urn:nbn:de:0030-drops-129424
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12942/
Go to the corresponding LIPIcs Volume Portal

Panagiotas, Ioannis ; Uçar, Bora

Engineering Fast Almost Optimal Algorithms for Bipartite Graph Matching

pdf-format:
LIPIcs-ESA-2020-76.pdf (0.7 MB)

Abstract

We consider the maximum cardinality matching problem in bipartite graphs. There are a number of exact, deterministic algorithms for this purpose, whose complexities are high in practice. There are randomized approaches for special classes of bipartite graphs. Random 2-out bipartite graphs, where each vertex chooses two neighbors at random from the other side, form one class for which there is an O(m+nlog n)-time Monte Carlo algorithm. Regular bipartite graphs, where all vertices have the same degree, form another class for which there is an expected O(m + nlog n)-time Las Vegas algorithm. We investigate these two algorithms and turn them into practical heuristics with randomization. Experimental results show that the heuristics are fast and obtain near optimal matchings. They are also more robust than the state of the art heuristics used in the cardinality matching algorithms, and are generally more useful as initialization routines.

BibTeX - Entry

@InProceedings{panagiotas_et_al:LIPIcs:2020:12942,
  author =	{Ioannis Panagiotas and Bora U{\c{c}}ar},
  title =	{{Engineering Fast Almost Optimal Algorithms for Bipartite Graph Matching}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{76:1--76:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12942},
  URN =		{urn:nbn:de:0030-drops-129424},
  doi =		{10.4230/LIPIcs.ESA.2020.76},
  annote =	{Keywords: bipartite graphs, matching, randomized algorithm}
}

Keywords: bipartite graphs, matching, randomized algorithm
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020
Supplementary Material: https://gitlab.inria.fr/bora-ucar/fast-matching

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI