A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
From MaRDI portal
Publication:4561265
DOI10.1137/17M1120920zbMath1401.05284arXiv1703.05598OpenAlexW2964074136MaRDI QIDQ4561265
Rolf Niedermeier, George B. Mertzios, André Nichterlein
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
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)
Related Items (9)
The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ Unnamed Item ⋮ The power of linear-time data reduction for maximum matching ⋮ The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ Unnamed Item ⋮ On some graphs with a unique perfect matching ⋮ The Power of Linear-Time Data Reduction for Maximum Matching ⋮ Maximum matching in almost linear time on graphs of bounded clique-width
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new LBFS-based algorithm for cocomparability graph recognition
- Efficient algorithm for the vertex connectivity of trapezoid graphs
- The recognition of triangle graphs
- An O(\(n\)) time algorithm for maximum matching on cographs
- On the intersection of tolerance and cocomparability graphs
- An optimal greedy heuristic to color interval graphs
- Maximum weight bipartite matching in matrix multiplication time
- A linear-time algorithm for a special case of disjoint set union
- Matching theory
- Finding a maximum matching in a circular-arc graph
- Matching and multidimensional matching in chordal and strongly chordal graphs
- Efficient graph representations
- Extending partial representations of trapezoid graphs
- Maximum skew-symmetric flows and matchings
- Algorithmic graph theory and perfect graphs
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- A linear time algorithm for maximum matchings in convex, bipartite graphs
- Maximum matching in regular and almost regular graphs
- Recognizing simple-triangle graphs by restricted 2-chain subgraph cover
- An intersection model for multitolerance graphs: efficient algorithms and hierarchy
- Vertex splitting and the recognition of trapezoid graphs
- Maximum matchings in planar graphs via Gaussian elimination
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- On the Power of Graph Searching for Cocomparability Graphs
- New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs
- LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
- A New Intersection Model and Improved Algorithms for Tolerance Graphs
- The Recognition of Tolerance and Bounded Tolerance Graphs
- Domination on Cocomparability Graphs
- Linear Time LexDFS on Cocomparability Graphs.
- Linear-Time Approximation for Maximum Weight Matching
- A Unified View of Graph Searching
- Graph Classes: A Survey
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- On the 2-Chain Subgraph Cover and Related Problems
- Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
- Feedback vertex set on cocomparability graphs
- A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
- The Power of Linear-Time Data Reduction for Maximum Matching
- Algorithms – ESA 2004
- The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Parameterized aspects of triangle enumeration
- When can graph hyperbolicity be computed in linear time?
This page was built for publication: A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs
