Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments

DOI10.4230/LIPIcs.ESA.2018.53OpenAlexW2810035363MaRDI QIDQ5009617

Rolf Niedermeier, André Nichterlein, Philipp Zschoche, Viatcheslav Korenwein

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1806.09683

zbMATH Keywords

linear-time algorithmskernelizationpreprocessingmaximum-weight matchingparameterized complexity analysismaximum-cardinality matching

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (8)

Data Reduction for Maximum Matching on Real-World Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The power of linear-time data reduction for maximum matching ⋮ An Adaptive Version of Brandes' Algorithm for Betweenness Centrality ⋮ Dynamic Matching Algorithms in Practice ⋮ Parameterized aspects of triangle enumeration ⋮ On the König deficiency of zero-reducible graphs

Uses Software

• SNAP
• Blossom V

Cites Work

• Unnamed Item
• Unnamed Item
• Blossom V: A new implementation of a minimum cost perfect matching algorithm
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Matching is as easy as matrix inversion
• Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs
• Crown structures for vertex cover kernelization
• Linear-Time Approximation for Maximum Weight Matching
• Scaling Algorithms for Weighted Matching in General Graphs
• The Power of Linear-Time Data Reduction for Maximum Matching
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Combinatorial optimization. Theory and algorithms

This page was built for publication: Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments