Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time

DOI10.7151/dmgt.2336zbMath1493.05225OpenAlexW3034287555MaRDI QIDQ2158196

Andreas Brandstädt, Raffaele Mosca

Publication date: 26 July 2022

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7151/dmgt.2336

zbMATH Keywords

polynomial time algorithmdominating induced matching\(P_9\)-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Computational complexity aspects of super domination ⋮ Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time

Cites Work

• Dominating induced matchings for \(P_7\)-free graphs in linear time
• Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time
• Dominating cliques in \(P_ 5\)-free graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Efficient edge domination problems in graphs
• Perfect edge domination and efficient edge domination in graphs
• Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs
• Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
• Dominating induced matchings in graphs without a skew star
• Perfect codes in graphs
• Efficient Edge Domination on Hole-Free Graphs in Polynomial Time
• Dominating induced matchings in graphs containing no long claw