Back to Search
Start Over
A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
- Publication Year :
- 2017
-
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 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).<br />Comment: 16 pages, 4 figures. to appear at SIDMA arXiv admin note: text overlap with arXiv:1609.08879
- Subjects :
- Computer Science - Data Structures and Algorithms
F.2.2
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1703.05598
- Document Type :
- Working Paper