Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/96230
DC FieldValueLanguage
dc.contributor.authorMartins, Lúcia-
dc.contributor.authorSantos, Dorabella-
dc.contributor.authorGomes, Teresa-
dc.contributor.authorGirão-Silva, Rita-
dc.date.accessioned2021-10-31T09:52:21Z-
dc.date.available2021-10-31T09:52:21Z-
dc.date.issued2021-10-21-
dc.identifier.issn2169-3536pt
dc.identifier.urihttp://hdl.handle.net/10316/96230-
dc.description.abstractWe 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.sponsorshipThis 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.isoengpt
dc.publisherIEEEpt
dc.relationCENTRO-01-0145-FEDER-029312pt
dc.rightsopenAccesspt
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/pt
dc.subjectDelay-constrainedpt
dc.subjectGraph reductionspt
dc.subjectHeuristicpt
dc.subjectInteger linear programmingpt
dc.subjectSteiner tree problempt
dc.titleDetermining the Minimum Cost Steiner Tree for Delay Constrained Problemspt
dc.typearticle-
degois.publication.firstPage144927pt
degois.publication.lastPage144939pt
degois.publication.titleIEEE Accesspt
dc.relation.publisherversionhttps://ieeexplore.ieee.org/document/9583293pt
dc.peerreviewedyespt
dc.identifier.doi10.1109/ACCESS.2021.3122024pt
degois.publication.volume9pt
dc.date.embargo2021-10-21*
uc.date.periodoEmbargo0pt
item.fulltextCom Texto completo-
item.grantfulltextopen-
item.languageiso639-1en-
crisitem.author.deptFaculty of Sciences and Technology-
crisitem.author.deptFaculty of Sciences and Technology-
crisitem.author.deptFaculty of Sciences and Technology-
crisitem.author.parentdeptUniversity of Coimbra-
crisitem.author.parentdeptUniversity of Coimbra-
crisitem.author.parentdeptUniversity of Coimbra-
crisitem.author.researchunitINESC Coimbra – Institute for Systems Engineering and Computers at Coimbra-
crisitem.author.researchunitINESC Coimbra – Institute for Systems Engineering and Computers at Coimbra-
crisitem.author.researchunitINESC Coimbra – Institute for Systems Engineering and Computers at Coimbra-
crisitem.author.researchunitINESC Coimbra – Institute for Systems Engineering and Computers at Coimbra-
crisitem.author.orcid0000-0002-6534-0159-
crisitem.author.orcid0000-0003-0368-2222-
crisitem.author.orcid0000-0002-3084-5608-
crisitem.author.orcid0000-0002-2331-8340-
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 simple item record

Page view(s)

105
checked on Sep 30, 2022

Download(s)

126
checked on Sep 30, 2022

Google ScholarTM

Check

Altmetric

Altmetric


This item is licensed under a Creative Commons License Creative Commons