2026-07-23T21:02:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9516 2024-03-06T10:43:56Z ddc:004 open_access

Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments Korenwein, Viatcheslav Nichterlein, André Niedermeier, Rolf Zschoche, Philipp Maximum-cardinality matching maximum-weight matching linear-time algorithms preprocessing kernelization parameterized complexity analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Viatcheslav Korenwein and André Nichterlein and Rolf Niedermeier and Philipp Zschoche 2018 Is Part Of LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2018.53 urn:nbn:de:0030-drops-95169 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.53 eng https://creativecommons.org/licenses/by/3.0/legalcode