Article: A tree-block decomposition-based heuristic for the minimum broadcast time Journal: International Journal of Metaheuristics (IJMHEUR) 2020 Vol.7 No.4 pp.379 - 401 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 <i>NP</i>-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 <i>TreeBlock</i>, is developed. A fair comparison between TreeBlock and previous heuristics highlights the effectiveness of our proposal. Inderscience Publishers - linking academia, business and industry through research

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: 03 Dec 2020 *

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

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

Keep up-to-date