On the complexity of broadcast domination and multipacking In digraphs

DOI10.1007/s00453-021-00828-5OpenAlexW3166525196MaRDI 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

Mathematics Subject Classification ID

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

Related Items (2)

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

This page was built for publication: On the complexity of broadcast domination and multipacking In digraphs