The Power of Linear-Time Data Reduction for Maximum Matching

Mertzios, G.B.; Nichterlein, A.; Niedermeier, R.

doi:10.1007/s00453-020-00736-0

The Power of Linear-Time Data Reduction for Maximum Matching

Mertzios, G.B.; Nichterlein, A.; Niedermeier, R.

Authors

Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor

A. Nichterlein

R. Niedermeier

Abstract

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 still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.

Citation

Mertzios, G., Nichterlein, A., & Niedermeier, R. (2020). The Power of Linear-Time Data Reduction for Maximum Matching. Algorithmica, 82(12), 3521-3565. https://doi.org/10.1007/s00453-020-00736-0

Journal Article Type	Article
Acceptance Date	Jun 12, 2020
Online Publication Date	Jul 6, 2020
Publication Date	2020-12
Deposit Date	Jun 24, 2020
Publicly Available Date	Jul 15, 2020
Journal	Algorithmica
Print ISSN	0178-4617
Electronic ISSN	1432-0541
Publisher	Springer
Peer Reviewed	Peer Reviewed
Volume	82
Issue	12
Pages	3521-3565
DOI	https://doi.org/10.1007/s00453-020-00736-0

Files

Published Journal Article (Advance online version) (3.3 Mb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
Advance online version This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.