Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10316/96230
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor.author | Martins, Lúcia | - |
dc.contributor.author | Santos, Dorabella | - |
dc.contributor.author | Gomes, Teresa | - |
dc.contributor.author | Girão-Silva, Rita | - |
dc.date.accessioned | 2021-10-31T09:52:21Z | - |
dc.date.available | 2021-10-31T09:52:21Z | - |
dc.date.issued | 2021-10-21 | - |
dc.identifier.issn | 2169-3536 | pt |
dc.identifier.uri | https://hdl.handle.net/10316/96230 | - |
dc.description.abstract | We address a variant of the Steiner tree problem for delay constrained problems. The addressed problem consists in determining the minimum cost Steiner tree, while guaranteeing that the delay between any two terminal nodes does not exceed a given maximum value. This problem is known as the bounded diameter Steiner minimum tree problem. We propose a compact formulation based on integer linear programming (ILP) to obtain optimal solutions, which was efficiently solved on two telecommunication core networks up to 75 nodes. However, given that for traditional Steiner tree graphs the ILP proved to be inefficient, we propose a heuristic method and compare it with the ILP formulation. We show that the heuristic provides optimal solutions, except for two cases in our experiments where it provided near-optimal solutions, always in reasonable runtimes. Additionally, to reduce the complexity of the problem, we propose some novel and modified graph reductions specific for the addressed problem. | pt |
dc.description.sponsorship | This work was supported in part by European Regional Development Fund (ERDF) through the Centre's Regional Operational Program, and in part by the National Funds through Fundação para a Ciência e Tecnologia (FCT) under Project CENTRO-01-0145-FEDER-029312. | pt |
dc.language.iso | eng | pt |
dc.publisher | IEEE | pt |
dc.relation | CENTRO-01-0145-FEDER-029312 | pt |
dc.rights | openAccess | pt |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | pt |
dc.subject | Delay-constrained | pt |
dc.subject | Graph reductions | pt |
dc.subject | Heuristic | pt |
dc.subject | Integer linear programming | pt |
dc.subject | Steiner tree problem | pt |
dc.title | Determining the Minimum Cost Steiner Tree for Delay Constrained Problems | pt |
dc.type | article | - |
degois.publication.firstPage | 144927 | pt |
degois.publication.lastPage | 144939 | pt |
degois.publication.title | IEEE Access | pt |
dc.relation.publisherversion | https://ieeexplore.ieee.org/document/9583293 | pt |
dc.peerreviewed | yes | pt |
dc.identifier.doi | 10.1109/ACCESS.2021.3122024 | pt |
degois.publication.volume | 9 | pt |
dc.date.embargo | 2021-10-21 | * |
uc.date.periodoEmbargo | 0 | pt |
item.fulltext | Com Texto completo | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
item.languageiso639-1 | en | - |
item.openairetype | article | - |
item.cerifentitytype | Publications | - |
item.grantfulltext | open | - |
crisitem.author.researchunit | INESC Coimbra – Institute for Systems Engineering and Computers at Coimbra | - |
crisitem.author.researchunit | INESC Coimbra – Institute for Systems Engineering and Computers at Coimbra | - |
crisitem.author.researchunit | INESC Coimbra – Institute for Systems Engineering and Computers at Coimbra | - |
crisitem.author.researchunit | INESC Coimbra – Institute for Systems Engineering and Computers at Coimbra | - |
crisitem.author.orcid | 0000-0002-6534-0159 | - |
crisitem.author.orcid | 0000-0003-0368-2222 | - |
crisitem.author.orcid | 0000-0002-3084-5608 | - |
crisitem.author.orcid | 0000-0002-2331-8340 | - |
Aparece nas coleções: | FCTUC Eng.Electrotécnica - Artigos em Revistas Internacionais I&D INESCC - Artigos em Revistas Internacionais |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Determining_the_Minimum_Cost_Steiner_Tree_for_Delay_Constrained_Problems.pdf | Publisher version | 1.73 MB | Adobe PDF | Ver/Abrir |
Citações SCOPUSTM
4
Visto em 14/out/2024
Citações WEB OF SCIENCETM
3
Visto em 2/out/2024
Visualizações de página
183
Visto em 15/out/2024
Downloads
287
Visto em 15/out/2024
Google ScholarTM
Verificar
Altmetric
Altmetric
Este registo está protegido por Licença Creative Commons