Maximum induced matching algorithms via vertex ordering characterizations
From MaRDI portal
Publication:5136263
cocomparability graphsgraph classesindependent setfast algorithmsmaximum induced matchingvertex ordering characterization
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)
Recommendations
- Maximum induced matching algorithms via vertex ordering characterizations
- Maximum induced matchings for chordal graphs in linear time
- New results on induced matchings
- Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
- Exact algorithms for maximum induced matching
Cites work
- scientific article; zbMATH DE number 47161 (Why is no real title available?)
- A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
- A simple polynomial algorithm for the longest path problem on cocomparability graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithmic graph theory and perfect graphs
- Comparability graphs and intersection graphs
- Domination on Cocomparability Graphs
- Finding a maximum induced matching in weakly chordal graphs
- Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
- Graph Classes: A Survey
- Induced matchings
- Induced matchings in asteroidal triple-free graphs
- Induced matchings in intersection graphs.
- Irredundancy in circular arc graphs
- Joint congestion control and distributed scheduling for throughput guarantees in wireless networks
- LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
- Linear time LexDFS on cocomparability graphs
- Maximum induced matchings for chordal graphs in linear time
- Minimizing flow time in the wireless gathering problem
- Modular decomposition and transitive orientation
- NP-completeness of some generalizations of the maximum matching problem
- New results on induced matchings
- On maximum induced matchings in bipartite graphs
- On the approximability of the maximum induced matching problem
- On the np-completeness of certain network testing problems
- On the power of graph searching for cocomparability graphs
- Ordering without forbidden patterns
- The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
Cited in
(6)- Computing inductive vertex orderings
- Exact algorithms for maximum induced matching
- Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
- Maximum induced matchings for chordal graphs in linear time
- Maximum induced matching algorithms via vertex ordering characterizations
- Graph classes and forbidden patterns on three vertices
This page was built for publication: Maximum induced matching algorithms via vertex ordering characterizations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136263)
