Connectivity considerations in the design of survivable networks

The problem of constructing networks that are "survivable" with respect to branch damage is considered. The networks are modeled by linear graphs and a square symmetric "redundancy" matrix <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R'=[r'_ij]</tex> is specified. Algorithms are given to construct an undirected graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</tex> with a minimum number of branches such that 1) <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</tex> contains no parallel branches, and 2) for all <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i, j</tex> there are at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r'_ij</tex> branch disjoint paths between the ith and jth vertices. These algorithms are complicated but may easily be applied to construct graphs with several hundred vertices.