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

DOI10.1137/17M1120920MaRDI QIDQ4561265zbMATH OpenOpenAlexFDO

Authors George B. Mertzios, André Nichterlein, Rolf Niedermeier

Publication date 5 December 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

greedy algorithmsinterval graphslexicographic depth first searchperfect graphs

Mathematics Subject Classification ID

Perfect graphs (05C17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

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

Recommendations

• An optimal parallel matching algorithm for cographs
• Finding a maximum matching in a permutation graph
• Construction of a simple elimination scheme for a chordal comparability graph in linear time
• scientific article; zbMATH DE number 177842
• scientific article; zbMATH DE number 4101258

Cites work

• A linear time algorithm for maximum matchings in convex, bipartite graphs
• A linear-time algorithm for a special case of disjoint set union
• A new intersection model and improved algorithms for tolerance graphs
• A new LBFS-based algorithm for cocomparability graph recognition
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• A Unified View of Graph Searching
• Algorithmic graph theory and perfect graphs
• Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
• Algorithms – ESA 2004
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An intersection model for multitolerance graphs: efficient algorithms and hierarchy
• An O(n) time algorithm for maximum matching on cographs
• An optimal greedy heuristic to color interval graphs
• Domination on Cocomparability Graphs
• Efficient algorithm for the vertex connectivity of trapezoid graphs
• Efficient graph representations
• Extending partial representations of trapezoid graphs
• Feedback vertex set on cocomparability graphs
• Finding a maximum matching in a circular-arc graph
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• Graph Classes: A Survey
• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• scientific article; zbMATH DE number 1107732 (Why is no real title available?)
• scientific article; zbMATH DE number 2040948 (Why is no real title available?)
• scientific article; zbMATH DE number 6850484 (Why is no real title available?)
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Linear time LexDFS on cocomparability graphs
• Linear-time approximation for maximum weight matching
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Matching theory
• Maximum matching in regular and almost regular graphs
• Maximum matchings in planar graphs via Gaussian elimination
• Maximum skew-symmetric flows and matchings
• Maximum weight bipartite matching in matrix multiplication time
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• New geometric representations and domination problems on tolerance and multitolerance graphs
• On the 2-Chain Subgraph Cover and Related Problems
• On the intersection of tolerance and cocomparability graphs
• On the power of graph searching for cocomparability graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• The Power of Linear-Time Data Reduction for Maximum Matching
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• The recognition of tolerance and bounded tolerance graphs
• The recognition of triangle graphs
• Vertex splitting and the recognition of trapezoid graphs
• When can graph hyperbolicity be computed in linear time?

Cited in

(15)

• On some graphs with a unique perfect matching
• Maximum induced matching algorithms via vertex ordering characterizations
• Maximum matching in almost linear time on graphs of bounded clique-width
• The power of linear-time data reduction for maximum matching
• The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• scientific article; zbMATH DE number 5909229 (Why is no real title available?)
• scientific article; zbMATH DE number 1003276 (Why is no real title available?)
• scientific article; zbMATH DE number 1151797 (Why is no real title available?)
• On adaptive algorithms for maximum matching
• The Power of Linear-Time Data Reduction for Maximum Matching
• scientific article; zbMATH DE number 7651152 (Why is no real title available?)
• Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications
• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• Finding maximum matchings in RDV graphs efficiently

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)