Designing reliable networks with short paths

Abstract

We present a technique for constructing highly reliable networks in which locations consist of pairs of redundant vertices and in which every pair of locations has a pair of short disjoint paths connecting them. One of the paths between locations has one hop and, in most cases, the other path between locations has two hops. We further show that the networks have as few edges as possible and the vertices in the networks have nearly as small a degree as possible. © 1993 J.C. Baltzer AG, Science Publishers.