Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
From MaRDI portal
Publication:524382
DOI10.1007/s00453-016-0150-yzbMath1360.68497arXiv1908.00978OpenAlexW2342665464MaRDI QIDQ524382
Raffaele Mosca, Andreas Brandstädt
Publication date: 2 May 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1908.00978
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (7)
Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time ⋮ Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs ⋮ Modelling and solving the perfect edge domination problem ⋮ Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time ⋮ Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time
Cites Work
- 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
- 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
- Finding a maximum induced matching in weakly chordal graphs
- Algorithms for weakly triangulated 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
- Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
This page was built for publication: Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
