Tighter bounds on the minimum broadcast time

DOI10.1016/j.disopt.2024.100822OpenAlexW4390848319WikidataQ130030223 ScholiaQ130030223MaRDI QIDQ6122083

Dag Haugland

Publication date: 27 March 2024

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2024.100822

zbMATH Keywords

integer programmingboundsvalid inequalitiescommunication networkbroadcast timegreedy construction

Mathematics Subject Classification ID

Computer system organization (68Mxx) Theory of computing (68Qxx) Circuits, networks (94Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The minimum broadcast time problem for several processor networks
• Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
• Methods and problems of communication in usual networks
• An efficient heuristic for broadcasting in networks
• Broadcast Time in Communication Networks
• A data structure for manipulating priority queues
• Approximation Algorithms for Minimum-Time Broadcast
• On the facial structure of set packing polyhedra
• A matheuristic approach for the minimum broadcast time problem using a biased random‐key genetic algorithm

This page was built for publication: Tighter bounds on the minimum broadcast time