Answers are grounded in this paper and cite their sources.
We consider the problem of designing a network which satisfies a prespecified survivability criterion with minimum cost. The survivability criterion demands that there be at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">rᵢⱼ</tex> node disjoint paths between nodes <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</tex> , where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(rᵢⱼ)</tex> is a given redundancy requirement matrix. This design problem appears to be at least as difficult as the traveling salesman problem, and present techniques cannot provide a computationally feasible exact solution. A heuristic approach is described, based on recent work on the traveling salesman problem, which leads to a practical design method. Algorithms are described for generating starting networks, for producing local improvements in given networks, and for testing the redundancy of networks at each stage. This leads to networks which are locally optimum with respect to the given transformation. Randomizing the starting solution ensures that the solution space is widely sampled. Two theorems are given which allow great reduction in the amount of computation required to test the redundancy of a network. Finally, some design examples are given.
No takes yet. Share an insight, caveat, or question.
Steiglitz et al. (1969) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: