A linear‐time algorithm for broadcast domination in a tree

DOI10.1002/net.20275zbMath1175.68288OpenAlexW4243551981MaRDI QIDQ5191137

Brian C. Dean, Stephen T. Hedetniemi, John Dabney

Publication date: 28 July 2009

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20275

zbMATH Keywords

dominationlinear-time algorithmsbroadcaststree algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (18)

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 ⋮ 2-limited broadcast domination in subcubic graphs ⋮ Unnamed Item ⋮ New bounds for the broadcast domination number of a graph ⋮ On the broadcast independence number of grid graph ⋮ On the complexity of broadcast domination and multipacking In digraphs ⋮ Dominating and irredundant broadcasts in graphs ⋮ On the broadcast independence number of caterpillars ⋮ Broadcasts and domination in trees ⋮ Broadcast Domination in Graphs ⋮ Radial trees ⋮ 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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The level ancestor problem simplified
• Domination, independent domination, and duality in strongly chordal graphs
• Optimal broadcast domination in polynomial time
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Finding level-ancestors in trees
• Broadcasts in graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• Easy problems for tree-decomposable graphs
• Totally-Balanced and Greedy Matrices
• Doubly Lexical Orderings of Matrices
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Linear-time computation of optimal subgraphs of decomposable graphs

This page was built for publication: A linear‐time algorithm for broadcast domination in a tree