Finding The Shortest Node-Disjoint Pair of Paths That Are Allowed To Share Resilient Arcs
We have solved a problem of finding the shortest node-disjoint pair of paths that can share resilient arcs. It is assumed that a network consists of a set of nodes and a set of arcs. Moreover, a number of available arcs are resilient. Our goal is to find the shortest pair of paths such that they share only those nodes that are incident to shared resilient arcs. Furthermore, we assume that the resulting paths cannot contain loops. In the paper we present two novel algorithms solving the above problem. We implement the proposed algorithms and compare them to an MIP approach.