Survivable communication networks and the terminal capacity matrix

The problem of constructing networks that are "survivable" with respect to branch damage is considered. A square redundancy matrix <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R = [ri,j]</tex> is specified. Algorithms are given to construct a graph with minimum number of branches so that 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 1) at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ri,j</tex> undirected branch disjoint paths between the ith and the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</tex> th vertices, or 2) there are exactly <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ri,j</tex> undirected branch disjoint paths between the ith and the jth vertices. These algorithms are closely related to the optimal realization of terminal capacity matrices. Two of the algorithms are extended to the optimal realization of terminal capacity matrices for symmetric or pseudosymmetric graphs.