Creating and sharing knowledge for telecommunications

A tree-block decomposition-based heuristic for the minimum broadcast time

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

international journal of metaheuristics Vol. 7, Nº 4, pp. 379 - 401, November, 2020.

ISSN (print): 1755-2176
ISSN (online): 1755-2184

Journal Impact Factor: (in )

Digital Object Identifier: 10.1504/IJMHEUR.2020.111611

The problem under study is the minimum broadcast time. Given an undirected connected graph and a singleton that owns a message, the goal is to broadcast this message as soon as possible, where the communication takes place between neighbouring-nodes in a selective fashion and each forwarding takes one time-slot. Historically, this problem finds applications in telephonic services; however, it serves as an inspirational problem for the design of current delay-tolerant forwarding schemes in modern communication systems like content delivery networks and peer-to-peer networks. The problem belongs to the NP-complete class. As a consequence, the literature offers heuristics, approximation algorithms and exact exponential-time solutions. The contributions of this paper are two-fold. First, an efficient integer linear programming formulation for the problem is provided. Second, a competitive heuristic called TreeBlock, is developed. A fair comparison between TreeBlock and previous heuristics highlights the effectiveness of our proposal.