1 Search Results for "Korenwein, Viatcheslav"

Document
DOI: 10.4230/LIPIcs.ESA.2018.53
Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments

Authors: Viatcheslav Korenwein, André Nichterlein, Rolf Niedermeier, and Philipp Zschoche

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Finding a maximum-cardinality or maximum-weight matching in (edge-weighted) undirected graphs is among the most prominent problems of algorithmic graph theory. For n-vertex and m-edge graphs, the best known algorithms run in O~(m sqrt{n}) time. We build on recent theoretical work focusing on linear-time data reduction rules for finding maximum-cardinality matchings and complement the theoretical results by presenting and analyzing (thereby employing the kernelization methodology of parameterized complexity analysis) linear-time data reduction rules for the positive-integer-weighted case. Moreover, we experimentally demonstrate that these data reduction rules provide significant speedups of the state-of-the art implementation for computing matchings in real-world graphs: the average speedup is 3800% in the unweighted case and "just" 30% in the weighted case.
Cite as

Viatcheslav Korenwein, André Nichterlein, Rolf Niedermeier, and Philipp Zschoche. Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 53:1-53:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{korenwein_et_al:LIPIcs.ESA.2018.53,
  author =	{Korenwein, Viatcheslav and Nichterlein, Andr\'{e} and Niedermeier, Rolf and Zschoche, Philipp},
  title =	{{Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{53:1--53:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.53},
  URN =		{urn:nbn:de:0030-drops-95169},
  doi =		{10.4230/LIPIcs.ESA.2018.53},
  annote =	{Keywords: Maximum-cardinality matching, maximum-weight matching, linear-time algorithms, preprocessing, kernelization, parameterized complexity analysis}
}
  • Refine by Author
  • 1 Korenwein, Viatcheslav
  • 1 Nichterlein, André
  • 1 Niedermeier, Rolf
  • 1 Zschoche, Philipp

  • Refine by Classification
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Maximum-cardinality matching
  • 1 kernelization
  • 1 linear-time algorithms
  • 1 maximum-weight matching
  • 1 parameterized complexity analysis
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact