Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time

DOI10.1016/J.DAM.2020.03.043zbMath1443.05137arXiv1905.05582OpenAlexW3014681787MaRDI QIDQ777392

Andreas Brandstädt, Raffaele Mosca

Publication date: 7 July 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1905.05582

zbMATH Keywords

polynomial time algorithm\(S_{1, 1, 5}\)-free graphs

Mathematics Subject Classification ID

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 (2)

Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time ⋮ 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
• 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
• 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

This page was built for publication: Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time