Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/48006
Title: Algorithms for determining a node-disjoint path pair visiting specified nodes
Authors: Gomes, Teresa 
Martins, Lúcia 
Ferreira, Sofia 
Pascoal, Marta 
Tipper, David 
Issue Date: 2017
Publisher: Elsevier
Project: info:eu-repo/grantAgreement/FCT/5876/147388/PT 
QREN 23301 PANORAMA II 
Serial title, monograph or event: Optical Switching and Networking
Volume: 23
Abstract: The 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.
Description: Algorithms for determining a node-disjoint path pair visiting specified nodes
URI: http://hdl.handle.net/10316/48006
Rights: embargoedAccess
Appears in Collections:FCTUC Eng.Electrotécnica - Artigos em Revistas Internacionais
I&D INESCC - Artigos em Revistas Internacionais

Files in This Item:
File Description SizeFormat Login
Gomes-et-al_OSN2017_EstudoGeral.pdf1.17 MBAdobe PDFEmbargo Access    Request a copy
Show full item record

Page view(s) 50

286
checked on Oct 15, 2019

Download(s) 50

321
checked on Oct 15, 2019

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons