A linear‐time algorithm for broadcast domination in a tree
From MaRDI portal
Publication:5191137
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
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