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 TamanhoFormato
Determining_the_Minimum_Cost_Steiner_Tree_for_Delay_Constrained_Problems.pdfPublisher version1.73 MBAdobe PDFVer/Abrir
Mostrar registo em formato completo

Citações SCOPUSTM   

3
Visto em 26/fev/2024

Citações WEB OF SCIENCETM

3
Visto em 2/mar/2024

Visualizações de página

149
Visto em 26/mar/2024

Downloads

221
Visto em 26/mar/2024

Google ScholarTM

Verificar

Altmetric

Altmetric


Este registo está protegido por Licença Creative Commons Creative Commons