Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/96230
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.
URI: http://hdl.handle.net/10316/96230
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)

100
checked on Aug 5, 2022

Download(s)

117
checked on Aug 5, 2022

Google ScholarTM

Check

Altmetric

Altmetric


This item is licensed under a Creative Commons License Creative Commons