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):
Scimago Journal Ranking: 0,35 (in 2018)
Digital Object Identifier: 10.1016/j.endm.2018.07.022
Abstract
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.
