Maximum induced matching algorithms via vertex ordering characterizations
DOI10.4230/LIPICS.ISAAC.2017.43zbMATH Open1457.68217OpenAlexW4392618871MaRDI QIDQ5136263FDOQ5136263
Publication date: 25 November 2020
Full work available at URL: https://hal.inria.fr/hal-01672520
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
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)
Cites Work
- Graph Classes: A Survey
- Comparability graphs and intersection graphs
- Modular decomposition and transitive orientation
- Algorithmic graph theory and perfect graphs
- A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
- LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
- Domination on Cocomparability Graphs
- A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
- Induced matchings
- On maximum induced matchings in bipartite graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Induced matchings in asteroidal triple-free graphs
- NP-completeness of some generalizations of the maximum matching problem
- 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
- On the approximability of the maximum induced matching problem
- New results on induced matchings
- Maximum induced matchings for chordal graphs in linear time
- Induced matchings in intersection graphs.
- Finding a maximum induced matching in weakly chordal graphs
- On the power of graph searching for cocomparability graphs
- Title not available (Why is that?)
- Joint congestion control and distributed scheduling for throughput guarantees in wireless networks
- The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
- Irredundancy in circular arc graphs
- Minimizing flow time in the wireless gathering problem
- On the np-completeness of certain network testing problems
- A new graph parameter to measure linearity
- Linear Time LexDFS on Cocomparability Graphs.
- Ordering without Forbidden Patterns
Cited In (5)
- Exact algorithms for maximum induced matching
- Maximum induced matching algorithms via vertex ordering characterizations
- Maximum induced matchings for chordal graphs in linear time
- Graph Classes and Forbidden Patterns on Three Vertices
- Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
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)
