Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/96230
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Martins, Lúcia | - |
dc.contributor.author | Santos, Dorabella | - |
dc.contributor.author | Gomes, Teresa | - |
dc.contributor.author | Girão-Silva, Rita | - |
dc.date.accessioned | 2021-10-31T09:52:21Z | - |
dc.date.available | 2021-10-31T09:52:21Z | - |
dc.date.issued | 2021-10-21 | - |
dc.identifier.issn | 2169-3536 | pt |
dc.identifier.uri | https://hdl.handle.net/10316/96230 | - |
dc.description.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. | pt |
dc.description.sponsorship | This 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.iso | eng | pt |
dc.publisher | IEEE | pt |
dc.relation | CENTRO-01-0145-FEDER-029312 | pt |
dc.rights | openAccess | pt |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | pt |
dc.subject | Delay-constrained | pt |
dc.subject | Graph reductions | pt |
dc.subject | Heuristic | pt |
dc.subject | Integer linear programming | pt |
dc.subject | Steiner tree problem | pt |
dc.title | Determining the Minimum Cost Steiner Tree for Delay Constrained Problems | pt |
dc.type | article | - |
degois.publication.firstPage | 144927 | pt |
degois.publication.lastPage | 144939 | pt |
degois.publication.title | IEEE Access | pt |
dc.relation.publisherversion | https://ieeexplore.ieee.org/document/9583293 | pt |
dc.peerreviewed | yes | pt |
dc.identifier.doi | 10.1109/ACCESS.2021.3122024 | pt |
degois.publication.volume | 9 | pt |
dc.date.embargo | 2021-10-21 | * |
uc.date.periodoEmbargo | 0 | pt |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
item.openairetype | article | - |
item.cerifentitytype | Publications | - |
item.grantfulltext | open | - |
item.fulltext | Com Texto completo | - |
item.languageiso639-1 | en | - |
crisitem.author.dept | Faculty of Sciences and Technology | - |
crisitem.author.parentdept | University of Coimbra | - |
crisitem.author.researchunit | INESC Coimbra – Institute for Systems Engineering and Computers at Coimbra | - |
crisitem.author.researchunit | INESC Coimbra – Institute for Systems Engineering and Computers at Coimbra | - |
crisitem.author.researchunit | INESC Coimbra – Institute for Systems Engineering and Computers at Coimbra | - |
crisitem.author.researchunit | INESC Coimbra – Institute for Systems Engineering and Computers at Coimbra | - |
crisitem.author.orcid | 0000-0002-6534-0159 | - |
crisitem.author.orcid | 0000-0003-0368-2222 | - |
crisitem.author.orcid | 0000-0002-3084-5608 | - |
crisitem.author.orcid | 0000-0002-2331-8340 | - |
Appears in Collections: | FCTUC Eng.Electrotécnica - Artigos em Revistas Internacionais I&D INESCC - Artigos em Revistas Internacionais |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Determining_the_Minimum_Cost_Steiner_Tree_for_Delay_Constrained_Problems.pdf | Publisher version | 1.73 MB | Adobe PDF | View/Open |
SCOPUSTM
Citations
3
checked on Apr 1, 2024
WEB OF SCIENCETM
Citations
3
checked on Apr 2, 2024
Page view(s)
160
checked on Apr 16, 2024
Download(s)
228
checked on Apr 16, 2024
Google ScholarTM
Check
Altmetric
Altmetric
This item is licensed under a Creative Commons License