Please use this identifier to cite or link to this item: https://hdl.handle.net/10316/48006
DC FieldValueLanguage
dc.contributor.authorGomes, Teresa-
dc.contributor.authorMartins, Lúcia-
dc.contributor.authorFerreira, Sofia-
dc.contributor.authorPascoal, Marta-
dc.contributor.authorTipper, David-
dc.date.accessioned2018-03-19T10:37:03Z-
dc.date.issued2017-
dc.identifier.urihttps://hdl.handle.net/10316/48006-
dc.descriptionAlgorithms for determining a node-disjoint path pair visiting specified nodespor
dc.description.abstractThe problem of calculating the shortest path that visits a given set of nodes is at least as difficult as the traveling salesman problem, and it has not received much attention. Nevertheless an efficient integer linear programming (ILP) formulation has been recently proposed for this problem. That ILP formulation is firstly adapted to include the constraint that the obtained path can be protected by a node-disjoint path, and secondly to obtain a pair of node disjoint paths, of minimal total additive cost, each having to visit a given set of specified nodes. Computational experiments show that these approaches, namely in large networks, may fail to obtain solutions in a reasonable amount of time. Therefore heuristics are proposed for solving those problems, that may arise due to network management constraints. Extensive computational results show that they are capable of finding a solution in most cases, and that the calculated solutions present an acceptable relative error regarding the cost of the obtained path or pair of paths. Further the CPU time required by the heuristics is significantly smaller than the required by the used ILP solver.por
dc.description.sponsorshipThe authors acknowledge financial support through project QREN 23301 PANORAMA II, co-financed by European Unions FEDER through “Programa Operacional Factores de Competitividade” (POFC) of QREN (FCOMP-01-0202-FEDER-023301) and by Fundação para a Ciência e a Tecnologia (FCT) under project Grant UID/MULTI/00308/2013.por
dc.language.isoengpor
dc.publisherElsevierpor
dc.relationinfo:eu-repo/grantAgreement/FCT/5876/147388/PTpor
dc.relationQREN 23301 PANORAMA IIpor
dc.rightsembargoedAccess-
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/por
dc.titleAlgorithms for determining a node-disjoint path pair visiting specified nodespor
dc.typearticle-
degois.publication.firstPage189por
degois.publication.lastPage204por
degois.publication.titleOptical Switching and Networkingpor
dc.relation.publisherversionhttps://www.sciencedirect.com/science/article/abs/pii/S1573427716300194por
dc.peerreviewedyespor
dc.identifier.doi10.1016/j.osn.2016.05.002-
degois.publication.volume23por
dc.date.embargo2020-03-18T10:37:03Z-
rcaap.embargofctA revista em causa impõe um embargo de 48 meses sob versão pos-revisãopor
item.grantfulltextopen-
item.cerifentitytypePublications-
item.languageiso639-1en-
item.openairetypearticle-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.fulltextCom Texto completo-
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.researchunitINESC Coimbra – Institute for Systems Engineering and Computers at Coimbra-
crisitem.author.researchunitINESC Coimbra – Institute for Systems Engineering and Computers at Coimbra-
crisitem.author.researchunitCMUC - Centre for Mathematics of the University of Coimbra-
crisitem.author.orcid0000-0002-3084-5608-
crisitem.author.orcid0000-0002-6534-0159-
crisitem.author.orcid0000-0003-0517-677X-
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
Gomes-et-al_OSN2017_EstudoGeral.pdf1.17 MBAdobe PDFView/Open
Show simple item record

Google ScholarTM

Check

Altmetric

Altmetric


This item is licensed under a Creative Commons License Creative Commons