A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
George B. Mertzios, André Nichterlein, Rolf Niedermeier · SIAM Journal on Discrete Mathematics · 2018
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).