Finding dominating induced matchings in P₁₀-free graphs in polynomial time

DOI10.1016/J.TCS.2024.114404MaRDI QIDQ6201338zbMATH OpenOpenAlexWikidataFDO

Authors Andreas Brandstädt, Raffaele Mosca

Publication date 20 February 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2024.114404

zbMATH Keywords

polynomial time algorithmdominating induced matchingefficient edge domination\( P_{10}\)-free graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A characterization of graphs without long induced paths
• Dominating induced matching in some subclasses of bipartite 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 P₉-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

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

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