Finding dominating induced matchings in P₉-free graphs in polynomial time

DOI10.7151/DMGT.2336MaRDI QIDQ2158196zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Raffaele Mosca

Publication date 26 July 2022

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

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

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time
• Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
• Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
• Dominating induced matchings for \(P_7\)-free graphs in linear time
• On the complexity of the dominating induced matching problem in hereditary classes of graphs

Cites work

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

Cited in

(8)

• A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs
• Dominating induced matchings for \(P_7\)-free graphs in linear time
• Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
• Computational complexity aspects of super domination
• Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time
• Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time
• Graphs whose vertices of degree at least 2 lie in a triangle
• Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time

This page was built for publication: Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2158196)