Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Efficient Heuristics for Determining Node-Disjoint Path Pairs Visiting Specified Nodes

Martins, Lucia and Gomes, Teresa and Tipper, David (2017) Efficient Heuristics for Determining Node-Disjoint Path Pairs Visiting Specified Nodes. Networks, 70 (4). pp. 292-307.

Abstract

A new recursive heuristic is proposed to calculate a shortest simple path, from a source node to a destination node, that visits a specified set of nodes in a network. To provide survivability to failures along the path, the proposed heuristic is modified to ensure that the calculated path can be protected by a node‐disjoint backup path. Additionally, the case when both paths in the disjoint path pair are required to visit specific sets of nodes is studied and effective heuristics are proposed. An evaluation of the solutions of the heuristics is conducted by comparing with results from an integer linear programming (ILP) formulation for each of the considered problems, and also with previous heuristics. The ILP solver may require a significant amount of time to obtain a solution, especially in large networks, which justifies the need for effective, computationally efficient heuristics for solving these problems.


Share

Citation/Export:
Social Networking:
Share |

Details

Item Type: Article
Status: Published
Creators/Authors:
CreatorsEmailPitt UsernameORCID
Martins, Lucialucia@deec.uc.pt
Gomes, Teresateresa@deec.uc.pt
Tipper, Daviddtipper@pitt.eduDTIPPER
Date: 1 December 2017
Date Type: Publication
Journal or Publication Title: Networks
Volume: 70
Number: 4
Publisher: Wiley
Page Range: pp. 292-307
DOI or Unique Handle: 10.1002/net.21778
Schools and Programs: School of Computing and Information > Telecommunications
Refereed: Yes
Article Type: Research Article
Date Deposited: 10 Jul 2018 17:04
Last Modified: 10 Jul 2018 17:04
URI: http://d-scholarship.pitt.edu/id/eprint/34734

Metrics

Monthly Views for the past 3 years

Plum Analytics

Altmetric.com


Actions (login required)

View Item View Item