Weighted efficient domination in two subclasses of \(P_6\)-free graphs

DOI10.1016/j.dam.2015.07.032zbMath1329.05225OpenAlexW1174822088MaRDI QIDQ908292

T. Karthick, Andreas Brandstädt

Publication date: 4 February 2016

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

Full work available at URL: https://doi.org/10.1016/j.dam.2015.07.032

zbMATH Keywords

graph algorithmsperfect codeefficient dominationdomination in graphs\(P_6\)-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

One-three join: a graph operation and its consequences ⋮ Structure of squares and efficient domination in graph classes ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs ⋮ Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets in classes related to claw-free graphs
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• On independent vertex sets in subclasses of apple-free graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Efficient edge domination problems in graphs
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
• Weighted efficient domination problem on some perfect graphs
• Weighted domination of cocomparability graphs
• Weighted independent perfect domination on cocomparability graphs
• The weighted perfect domination problem and its variants
• A note on efficient domination in a superclass of \(P_5\)-free graphs
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Perfect codes in graphs
• New Polynomial Cases of the Weighted Efficient Domination Problem
• Graph Classes: A Survey
• Independence and Efficient Domination on P₆-free Graphs
• New Polynomial Case for Efficient Domination in P 6-free Graphs
• Hereditary Efficiently Dominatable Graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• Multiplying matrices faster than coppersmith-winograd
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Weighted efficient domination in two subclasses of \(P_6\)-free graphs