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 graphsgraph classesindependent setfast algorithmsmaximum induced matchingvertex ordering characterization

Mathematics Subject Classification ID

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)

• Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
• Computing inductive vertex orderings
• Graph classes and forbidden patterns on three vertices
• Exact algorithms for maximum induced matching
• Maximum induced matching algorithms via vertex ordering characterizations
• Maximum induced matchings for chordal graphs in linear time

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)