On the complexity of broadcast domination and multipacking in digraphs
From MaRDI portal
Publication:1979448
DOI10.1007/S00453-021-00828-5OpenAlexW3166525196MaRDI QIDQ1979448FDOQ1979448
Authors: Florent Foucaud, Benjamin Gras, Anthony Perez, Florian Sikora 
Publication date: 2 September 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2003.10570
Recommendations
- On the complexity of \textsc{broadcast domination} and \textsc{Multipacking} in digraphs
- Broadcast domination and multipacking: bounds and the integrality gap
- \(k\)-broadcast domination and \(k\)-multipacking
- On the difference between broadcast and multipacking numbers of graphs
- Dominating 2-broadcast in graphs: Complexity, bounds and extremal graphs
Cites Work
- Title not available (Why is that?)
- Exact exponential algorithms.
- Planar 3DM is NP-complete
- Parameterized algorithms
- Title not available (Why is that?)
- Some simplified NP-complete graph problems
- Kernelization lower bounds through colors and IDs
- Sparsity. Graphs, structures, and algorithms
- Kernel bounds for disjoint cycles and disjoint paths
- Faster fixed-parameter tractable algorithms for matching and packing problems
- Broadcasts in graphs
- Title not available (Why is that?)
- Optimal broadcast domination in polynomial time
- New bounds for the broadcast domination number of a graph
- Title not available (Why is that?)
- A linear‐time algorithm for broadcast domination in a tree
- On the multipacking number of grid graphs
- Title not available (Why is that?)
- General bounds on limited broadcast domination
- Broadcast domination and multipacking in strongly chordal graphs
- Broadcast domination on block graphs in linear time
- Resolving conflicts for lower-bounded clustering
- On the complexity of \textsc{broadcast domination} and \textsc{Multipacking} in digraphs
- Broadcast domination and multipacking: bounds and the integrality gap
Cited In (10)
- Title not available (Why is that?)
- On directed covering and domination problems
- On directed covering and domination problems
- Dominating 2-broadcast in graphs: Complexity, bounds and extremal graphs
- Broadcast domination and multipacking: bounds and the integrality gap
- The complexity of broadcasting in planar and decomposable graphs
- \(k\)-broadcast domination and \(k\)-multipacking
- Graph-Theoretic Concepts in Computer Science
- On the complexity of \textsc{broadcast domination} and \textsc{Multipacking} in digraphs
- Relation between broadcast domination and multipacking numbers on chordal graphs
This page was built for publication: On the complexity of broadcast domination and multipacking in digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1979448)
