A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs

DOI10.1137/17M1120920zbMATH Open1401.05284arXiv1703.05598OpenAlexW2964074136MaRDI QIDQ4561265

Author name not available (Why is that?)

Publication date: 5 December 2018

Published in: (Search for Journal in Brave)

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(msqrtn)$ time. We develop a linear-time algorithm to find maximum-cardinality matchings on cocomparability graphs, a prominent subclass of perfect graphs that contains interval graphs as well as permutation graphs. Our algorithm is based on the recently discovered Lexicographic Depth First Search (LDFS).

Full work available at URL: https://arxiv.org/abs/1703.05598

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4561265)