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

Authors: Amaro De Sousa; Gabriela Gallo; Santiago Gutiérrez; Franco Robledo; Pablo Rodrı́guez-Bocca; Pablo Romero

Addresses: Departamento de Eletrónica, Instituto de Telecomunicações, Telecomunicações e Informática, Universidade de Aveiro, Aveiro, Portugal ' Facultad de Ingeniería, Instituto de Computación, Universidad de la República, Montevideo, Uruguay ' Facultad de Ingeniería, Instituto de Computación, Universidad de la República, Montevideo, Uruguay ' Facultad de Ingeniería, Instituto de Computación, Universidad de la República, Montevideo, Uruguay ' Facultad de Ingeniería, Instituto de Computación, Universidad de la República, Montevideo, Uruguay ' Facultad de Ingeniería, Instituto de Computación, Universidad de la República, Montevideo, Uruguay

Abstract: 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.

Keywords: minimum broadcast time; MBT; computational complexity; integer linear programming; ILP; heuristics.

DOI: 10.1504/IJMHEUR.2020.111611

International Journal of Metaheuristics, 2020 Vol.7 No.4, pp.379 - 401

Received: 05 Aug 2019
Accepted: 12 Jun 2020

Published online: 26 Nov 2020 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article