Maximum Induced Matching Algorithms via Vertex Ordering Characterizations

DOI10.4230/LIPIcs.ISAAC.2017.43zbMath1457.68217OpenAlexW4392618871MaRDI QIDQ5136263

Lalla Mouatadid, Michel A. Habib

Publication date: 25 November 2020

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

zbMATH Keywords

fast algorithmsindependent setcocomparability graphsgraph classesmaximum induced matchingvertex ordering characterization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)

Related Items (2)

Maximum induced matching algorithms via vertex ordering characterizations ⋮ Graph Classes and Forbidden Patterns on Three Vertices

Cites Work

• Unnamed Item
• A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
• Irredundancy in circular arc graphs
• Maximum induced matchings for chordal graphs in linear time
• NP-completeness of some generalizations of the maximum matching problem
• Comparability graphs and intersection graphs
• Induced matchings
• Modular decomposition and transitive orientation
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• A new graph parameter to measure linearity
• 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
• Finding a maximum induced matching in weakly chordal graphs
• On maximum induced matchings in bipartite graphs
• Algorithmic graph theory and perfect graphs
• New results on induced matchings
• On the Power of Graph Searching for Cocomparability Graphs
• LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
• Ordering without Forbidden Patterns
• Domination on Cocomparability Graphs
• Linear Time LexDFS on Cocomparability Graphs.
• Minimizing flow time in the wireless gathering problem
• On the np-completeness of certain network testing problems
• The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Joint congestion control and distributed scheduling for throughput guarantees in wireless networks
• A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs

This page was built for publication: Maximum Induced Matching Algorithms via Vertex Ordering Characterizations