The Power of Linear-Time Data Reduction for Maximum Matching
(2020)
Journal Article
Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in O(mn−−√) time; however, for several applications this running time is... Read More about The Power of Linear-Time Data Reduction for Maximum Matching.