Broadcast domination and multipacking: bounds and the integrality gap

zbMath1419.05163arXiv1803.02550MaRDI QIDQ5197586

Laurent Beaudou, Richard C. Brewster, Florent Foucaud

Publication date: 19 September 2019

Full work available at URL: https://arxiv.org/abs/1803.02550

zbMATH Keywords

maximum weight packingminimum cost coverings

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

On the Complexity of Broadcast Domination and Multipacking in Digraphs ⋮ Broadcasts on paths and cycles ⋮ 2-limited broadcast domination on grid graphs ⋮ Relation between broadcast domination and multipacking numbers on chordal graphs ⋮ On the complexity of broadcast domination and multipacking In digraphs ⋮ Broadcast Domination in Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Broadcasts and domination in trees
• Domination, independent domination, and duality in strongly chordal graphs
• Optimal broadcast domination in polynomial time
• Radial trees
• Relations between packing and covering numbers of a tree
• New bounds for the broadcast domination number of a graph
• Broadcast domination and multipacking in strongly chordal graphs
• Broadcasts in graphs
• Combinatorial Optimization
• Doubly Lexical Orderings of Matrices
• A linear‐time algorithm for broadcast domination in a tree
• On the multipacking number of grid graphs

This page was built for publication: Broadcast domination and multipacking: bounds and the integrality gap