Properties of optimal survivable paths in a graph
We introduce the concept of a survivable path in an undirected graph G. A survivable path between a pair of vertices in C is a pair of edge-disjoint paths consisting of a working path and a redundant protection path. Protection paths share edges in such a manner as to provide guaranteed recovery upon the failure of any single edge. Survivable paths play an important role in the design of survivable communication networks. We demonstrate several results on the properties of the optimal set of survivable paths. (c) 2005 Elsevier Ltd. All rights reserved.
survivability undirected graph shortest paths routing optimization diverse routing multicommodity flow optical network