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

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

doi:10.1137/17m1120920

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

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