Skip to main content

Research Repository

Advanced Search

The Power of Linear-Time Data Reduction for Maximum Matching

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

The Power of Linear-Time Data Reduction for Maximum Matching Thumbnail


Authors

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
Public URL https://durham-repository.worktribe.com/output/1299117

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/.






You might also like



Downloadable Citations