We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

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

Mertzios, G.B. and Nichterlein, A. and Niedermeier, R. (2018) 'A linear-time algorithm for maximum-cardinality matching on cocomparability graphs.', SIAM journal on discrete mathematics., 32 (4). pp. 2820-2835.


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

Item Type:Article
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
Full text:(VoR) Version of Record
Download PDF
Publisher Web site:
Publisher statement:© 2018 SIAM.
Date accepted:02 October 2018
Date deposited:09 October 2018
Date of first online publication:04 December 2018
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar