Algorithms for finding an optimal set of short disjoint paths in a communication network

Abstract

The motives for seeking a set of short disjoint paths in a communication network are explained. A sequentially constructed optimal set is defined. Three efficient algorithms, one that constructs an optimal set and two that construct approximations, are presented. One of the latter algorithms not only constructs a larger set of short disjoint paths than an iterated version of the standard Dijkstra algorithm, but also offers a major reduction in computation time for large networks.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>