Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/33357
Título: | Heuristics for the Minimum Broadcast Time |
Autor: | Sousa, Amaro de Gallo, Gabriela Gutierrez, Santiago Robledo, Franco Rodríguez-Bocca, Pablo Romero, Pablo |
Palavras-chave: | Minimum Broadcast Time Computational complexity Heuristics |
Data: | Ago-2018 |
Editora: | Elsevier |
Resumo: | 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. |
Peer review: | yes |
URI: | http://hdl.handle.net/10773/33357 |
DOI: | 10.1016/j.endm.2018.07.022 |
ISSN: | 1571-0653 |
Aparece nas coleções: | IT - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
1-s2.0-S1571065318301665-main.pdf | Published version | 191.85 kB | Adobe PDF |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.