A dichotomy for weighted efficient dominating sets with bounded degree vertices

DOI10.1016/j.ipl.2018.10.007zbMath1469.68073OpenAlexW2896652362MaRDI QIDQ1628682

Andreas Brandstädt, Martin Milanič

Publication date: 5 December 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.10.007

zbMATH Keywords

polynomial-time algorithmgraph algorithmsweighted efficient domination\(k\)-bounded weighted efficient dominationbounded degree vertices

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• Generalized domination and efficient domination in graphs
• Weighted efficient domination problem on some perfect graphs
• Weighted independent perfect domination on cocomparability graphs
• The weighted perfect domination problem and its variants
• Perfect codes in graphs
• Efficient domination and efficient edge domination: a brief survey
• New Polynomial Cases of the Weighted Efficient Domination Problem
• Reducibility among Combinatorial Problems
• Hereditary Efficiently Dominatable Graphs

This page was built for publication: A dichotomy for weighted efficient dominating sets with bounded degree vertices