Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time

DOI10.1007/978-3-662-53174-7_6zbMath1417.05150OpenAlexW2116161556MaRDI QIDQ2827803

Elaine M. Eschen, Andreas Brandstädt, Erik Friese

Publication date: 21 October 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53174-7_6

zbMATH Keywords

polynomial-time algorithmchordal graphsefficient dominationhole-free graphs\(P_6\)-free graphs(house, hole, domino)-free graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

Weighted Efficient Domination for $$P_6$$ -Free and for $$P_5$$ -Free Graphs ⋮ Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time

Cites Work

• Unnamed Item
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• The strong perfect graph theorem
• Weighted efficient domination in two subclasses of \(P_6\)-free graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time
• New Polynomial Cases of the Weighted Efficient Domination Problem
• Graph Classes: A Survey
• Independence and Efficient Domination on P₆-free Graphs
• Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
• New Polynomial Case for Efficient Domination in P 6-free Graphs
• Hereditary Efficiently Dominatable Graphs

This page was built for publication: Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time