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

Tomohiro Koana, Viatcheslav Korenwein, André Nichterlein +2

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 $…