Premium
Shortest path problems with node failures
Author(s) -
Jaillet Patrick
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220607
Subject(s) - mathematics , shortest path problem , probabilistic logic , longest path problem , path (computing) , node (physics) , widest path problem , mathematical optimization , a priori and a posteriori , computer science , combinatorics , graph , structural engineering , engineering , programming language , philosophy , statistics , epistemology
Consider the problem of finding the shortest paths from a node source s to a node sink t in a complete network. On any given instance of the problem, only a subset of the intermediate nodes can be used to go from s to t , the subset being chosen according to a given probability law. We wish to find an a priori path from s to t such that, on any given instance of the problem, the sequence of nodes defining the path is preserved but only the permissible nodes are traversed, the others being skipped. The problem of finding an a priori path of minimum expected length is defined as the Probabilistic Shortest Path Problem (PSPP). Note that if the network is not originally complete, the PSPP methodology can still be used if we first add each missing edge, together with a deterministic length (being defined by an alternative path using nodes that have no probability of failure). In this paper, after discussing potential applications of the PSPP, we study the complexity of this class of problems. We first show that the problem is, in general, NP‐hard and then we develop polynomial time procedures for special cases of it. We also consider the complexity of a related problem: the Probabilistic Minimum Spanning Tree Problem (PMSTP). Finally, we provide a discussion of the implications of the results.