Please use this identifier to cite or link to this item:
Title: Determining the Minimum Cost Steiner Tree for Delay Constrained Problems
Authors: Martins, Lúcia 
Santos, Dorabella 
Gomes, Teresa 
Girão-Silva, Rita 
Keywords: Delay-constrained; Graph reductions; Heuristic; Integer linear programming; Steiner tree problem
Issue Date: 21-Oct-2021
Publisher: IEEE
Project: CENTRO-01-0145-FEDER-029312 
Serial title, monograph or event: IEEE Access
Volume: 9
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.
ISSN: 2169-3536
DOI: 10.1109/ACCESS.2021.3122024
Rights: openAccess
Appears in Collections:I&D INESCC - Artigos em Revistas Internacionais
FCTUC Eng.Electrotécnica - Artigos em Revistas Internacionais

Files in This Item:
File Description SizeFormat
Determining_the_Minimum_Cost_Steiner_Tree_for_Delay_Constrained_Problems.pdfPublisher version1.73 MBAdobe PDFView/Open
Show full item record

Page view(s)

checked on Mar 20, 2023


checked on Mar 20, 2023

Google ScholarTM




This item is licensed under a Creative Commons License Creative Commons