Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/33357
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Sousa, Amaro de | pt_PT |
dc.contributor.author | Gallo, Gabriela | pt_PT |
dc.contributor.author | Gutierrez, Santiago | pt_PT |
dc.contributor.author | Robledo, Franco | pt_PT |
dc.contributor.author | Rodríguez-Bocca, Pablo | pt_PT |
dc.contributor.author | Romero, Pablo | pt_PT |
dc.date.accessioned | 2022-03-04T10:45:35Z | - |
dc.date.available | 2022-03-04T10:45:35Z | - |
dc.date.issued | 2018-08 | - |
dc.identifier.issn | 1571-0653 | pt_PT |
dc.identifier.uri | http://hdl.handle.net/10773/33357 | - |
dc.description.abstract | 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. | pt_PT |
dc.language.iso | eng | pt_PT |
dc.publisher | Elsevier | pt_PT |
dc.relation | CSIC I+D 395 | pt_PT |
dc.rights | restrictedAccess | pt_PT |
dc.subject | Minimum Broadcast Time | pt_PT |
dc.subject | Computational complexity | pt_PT |
dc.subject | Heuristics | pt_PT |
dc.title | Heuristics for the Minimum Broadcast Time | pt_PT |
dc.type | article | pt_PT |
dc.description.version | published | pt_PT |
dc.peerreviewed | yes | pt_PT |
degois.publication.firstPage | 165 | pt_PT |
degois.publication.lastPage | 172 | pt_PT |
degois.publication.title | Electronic Notes in Discrete Mathematics | pt_PT |
degois.publication.volume | 69 | pt_PT |
dc.identifier.doi | 10.1016/j.endm.2018.07.022 | pt_PT |
Appears in Collections: | IT - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
1-s2.0-S1571065318301665-main.pdf | Published version | 191.85 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.