A linear-time algorithm for maximum-cardinality matching on cocomparability graphs

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

Abstract

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph problems. For general $m$-edge and $n$-vertex graphs, it is well known to be solvable in $O(m\sqrt{n})$ time. We present a linear-time algorithm to find maximum-cardinality matchings on cocomparability graphs, a prominent subclass of perfect graphs that strictly contains interval graphs as well as permutation graphs. Our greedy algorithm is based on the recently discovered Lexicographic Depth First Search (LDFS).

Citation

Mertzios, G., Nichterlein, A., & Niedermeier, R. (2018). A linear-time algorithm for maximum-cardinality matching on cocomparability graphs. SIAM Journal on Discrete Mathematics, 32(4), 2820-2835. https://doi.org/10.1137/17m1120920

• Journal Article Type: Article
• Acceptance Date: Oct 2, 2018
• Online Publication Date: Dec 4, 2018
• Publication Date: Dec 4, 2018
• Deposit Date: Oct 6, 2018
• Publicly Available Date: Jan 4, 2019
• Journal: SIAM Journal on Discrete Mathematics
• Print ISSN: 0895-4801
• Electronic ISSN: 1095-7146
• Publisher: Society for Industrial and Applied Mathematics
• Peer Reviewed: Peer Reviewed
• Volume: 32
• Issue: 4
• Pages: 2820-2835
• DOI: https://doi.org/10.1137/17m1120920
• Public URL: https://durham-repository.worktribe.com/output/1317406