On the complexity of broadcast domination and multipacking in digraphs

DOI10.1007/S00453-021-00828-5MaRDI QIDQ1979448zbMATH OpenOpenAlexFDO

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, https://basepub.dauphine.psl.eu/handle/123456789/22057

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

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

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 6843211 (Why is no real title available?)
• scientific article; zbMATH DE number 2170461 (Why is no real title available?)
• scientific article; zbMATH DE number 2109329 (Why is no real title available?)
• scientific article; zbMATH DE number 3299758 (Why is no real title available?)
• A linear‐time algorithm for broadcast domination in a tree
• Broadcast domination and multipacking in strongly chordal graphs
• Broadcast domination and multipacking: bounds and the integrality gap
• Broadcast domination on block graphs in linear time
• Broadcasts in graphs
• Exact exponential algorithms.
• Faster fixed-parameter tractable algorithms for matching and packing problems
• General bounds on limited broadcast domination
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization lower bounds through colors and IDs
• New bounds for the broadcast domination number of a graph
• On the complexity of \textsc{broadcast domination} and \textsc{Multipacking} in digraphs
• On the multipacking number of grid graphs
• Optimal broadcast domination in polynomial time
• Parameterized algorithms
• Planar 3DM is NP-complete
• Resolving conflicts for lower-bounded clustering
• Some simplified NP-complete graph problems
• Sparsity. Graphs, structures, and algorithms

Cited in

(10)

• Relation between broadcast domination and multipacking numbers on chordal graphs
• scientific article; zbMATH DE number 7021368 (Why is no real title available?)
• 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

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)