Maximum induced matching algorithms via vertex ordering characterizations

DOI10.4230/LIPICS.ISAAC.2017.43MaRDI QIDQ5136263zbMATH OpenOpenAlexFDO

Authors Lalla Mouatadid, M. A. Habib

Publication date 25 November 2020

Full work available at URL https://hal.inria.fr/hal-01672520

zbMATH Keywords

cocomparability graphsfast algorithmsgraph classesindependent setmaximum induced matchingvertex ordering characterization

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) 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)

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

• 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
• scientific article; zbMATH DE number 47161 (Why is no real title available?)
• 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
• New results on induced matchings
• NP-completeness of some generalizations of the maximum matching problem
• 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)

• Maximum induced matchings for chordal graphs in linear time
• Maximum induced matching algorithms via vertex ordering characterizations
• Computing inductive vertex orderings
• Exact algorithms for maximum induced matching
• Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
• 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)