Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10316/96230
Título: | Determining the Minimum Cost Steiner Tree for Delay Constrained Problems | Autor: | Martins, Lúcia Santos, Dorabella Gomes, Teresa Girão-Silva, Rita |
Palavras-chave: | Delay-constrained; Graph reductions; Heuristic; Integer linear programming; Steiner tree problem | Data: | 21-Out-2021 | Editora: | IEEE | Projeto: | CENTRO-01-0145-FEDER-029312 | Título da revista, periódico, livro ou evento: | IEEE Access | Volume: | 9 | Resumo: | 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. | URI: | https://hdl.handle.net/10316/96230 | ISSN: | 2169-3536 | DOI: | 10.1109/ACCESS.2021.3122024 | Direitos: | openAccess |
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