Cookies

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.

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

Item Type:Article
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
(439Kb)
Full text:(VoR) Version of Record
Download PDF
(406Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1137/17M1120920
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

Export:
Export
Look up in GoogleScholar