On the complexity of broadcast domination and multipacking In digraphs
From MaRDI portal
Publication:1979448
DOI10.1007/s00453-021-00828-5MaRDI QIDQ1979448
Anthony Perez, Benjamin Gras, Florian Sikora, Florent Foucaud
Publication date: 2 September 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2003.10570
Related Items
On the Complexity of Broadcast Domination and Multipacking in Digraphs, Relation between broadcast domination and multipacking numbers on chordal graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- Exact exponential algorithms.
- Kernel bounds for disjoint cycles and disjoint paths
- Optimal broadcast domination in polynomial time
- Faster fixed-parameter tractable algorithms for matching and packing problems
- Some simplified NP-complete graph problems
- New bounds for the broadcast domination number of a graph
- Broadcast domination and multipacking in strongly chordal graphs
- Broadcasts in graphs
- Broadcast Domination on Block Graphs in Linear Time
- Planar 3DM is NP-complete
- General bounds on limited broadcast domination
- Deciding First-Order Properties of Nowhere Dense Graphs
- Kernelization Lower Bounds Through Colors and IDs
- On the Complexity of Broadcast Domination and Multipacking in Digraphs
- A linear‐time algorithm for broadcast domination in a tree
- Broadcast domination and multipacking: bounds and the integrality gap
- On the multipacking number of grid graphs
- Parameterized Algorithms
