Creating and sharing knowledge for telecommunications

Heuristics for the Minimum Broadcast Time

Sousa, A. F. ; Gallo, G. ; Gutierrez, S. ; Robledo, F. ; Rodríguez-Bocca, P. ; Romero, P.

Electronic Notes in Discrete Mathematics Vol. 69, Nº -, pp. 165 - 172, August, 2018.

ISSN (print): 1571-0653
ISSN (online):

Journal Impact Factor: (in 0)

Digital Object Identifier: 10.1016/j.endm.2018.07.022

The problem under study is the Minimum Broadcast Time (MBT). We are given a simple graph and a singleton that owns a message. The goal is to disseminate the message as soon as possible, where the communication takes place between neighboring-nodes in a selective fashion and each forwarding takes one time-slot. The MBT serves as an inspirational problem for the design of delay-sensitive forwarding schemes. Since the problem belongs to the NP-Hard class, the literature offers heuristics, approximation algorithms and exact exponential-time solutions. The contributions of this paper are two-fold. First, an ILP formulation for the problem is provided. Second, a competitive heuristic is developed. A fair comparison between TreeBlock and previous heuristics highlights the effectiveness of our proposal.