Optimal broadcast domination in polynomial time
From MaRDI portal
Publication:856876
DOI10.1016/j.disc.2006.06.013zbMath1115.68115OpenAlexW1987801337MaRDI QIDQ856876
Daniel Lokshtanov, Pinar Heggernes
Publication date: 14 December 2006
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2006.06.013
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (30)
Algorithmic aspects of broadcast independence ⋮ On the Complexity of Broadcast Domination and Multipacking in Digraphs ⋮ Broadcast domination and multipacking in strongly chordal graphs ⋮ Broadcasts on paths and cycles ⋮ 2-limited broadcast domination on grid graphs ⋮ Relation between broadcast domination and multipacking numbers on chordal graphs ⋮ 2-limited broadcast domination in subcubic graphs ⋮ Global dominating broadcast in graphs ⋮ Unnamed Item ⋮ New bounds for the broadcast domination number of a graph ⋮ On the broadcast independence number of grid graph ⋮ A decomposition approach for solving a broadcast domination network design problem ⋮ On the complexity of broadcast domination and multipacking In digraphs ⋮ Exponential domination in subcubic graphs ⋮ Dominating 2-broadcast in graphs: Complexity, bounds and extremal graphs ⋮ Dominating and irredundant broadcasts in graphs ⋮ On the broadcast independence number of caterpillars ⋮ Broadcasts and domination in trees ⋮ A linear‐time algorithm for broadcast domination in a tree ⋮ Unnamed Item ⋮ On the broadcast domination number of permutation graphs ⋮ Bounds on the exponential domination number ⋮ \(k\)-broadcast domination and \(k\)-multipacking ⋮ Bounds on the sum of broadcast domination number and strong metric dimension of graphs ⋮ Broadcast Domination in Graphs ⋮ Radial trees ⋮ Relating broadcast independence and independence ⋮ Broadcast domination in subcubic graphs ⋮ Broadcast domination and multipacking: bounds and the integrality gap ⋮ 2-limited dominating broadcasts on cubic graphs without induced 4-cycles
Cites Work
This page was built for publication: Optimal broadcast domination in polynomial time
