Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/33356
Title: | A tree-block decomposition-based heuristic for the minimum broadcast time |
Author: | Sousa, Amaro de Gallo, Gabriela Gutiérrez, Santiago Robledo, Franco Rodríguez-Bocca, Pablo Romero, Pablo |
Keywords: | Minimum broadcast time MBT Computational complexity Integer linear programming ILP Heuristics |
Issue Date: | Nov-2020 |
Publisher: | Inderscience |
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. |
Peer review: | yes |
URI: | http://hdl.handle.net/10773/33356 |
DOI: | 10.1504/IJMHEUR.2020.111611 |
ISSN: | 1755-2176 |
Appears in Collections: | DETI - Artigos IT - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
IJMHEUR070404 ROMERO_263855.pdf | Published version | 883.34 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.