Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs

DOI10.1137/15M1039821zbMath1352.05143OpenAlexW2567413373MaRDI QIDQ2953402

Raffaele Mosca, Andreas Brandstädt

Publication date: 4 January 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1039821

zbMATH Keywords

polynomial time algorithmlinear time algorithm\(P_5\)-free graphsweighted efficient domination\(P_6\)-free graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Related Items (8)

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 ⋮ Revisiting Decomposition by Clique Separators ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ On efficient domination for some classes of \(H\)-free bipartite graphs

Cites Work

• Unnamed Item
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• Algorithms for unipolar and generalized split graphs
• The splittance of a graph
• Modular decomposition and transitive orientation
• Recognition of unipolar and generalised split graphs
• Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs
• Perfect codes in graphs
• Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time
• New Polynomial Cases of the Weighted Efficient Domination Problem
• Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs
• Independence and Efficient Domination on P₆-free Graphs
• Hereditary Efficiently Dominatable Graphs

This page was built for publication: Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs