The Design of Minimum-Cost Survivable Networks

摘要: We consider the problem of designing a network which satisfies prespecified survivability criterion with minimum cost. The demands that there be at least r_{ij} node disjoint paths between nodes i and j , where (r_{ij}) is given redundancy requirement matrix. This design appears to as difficult traveling salesman problem, present techniques cannot provide computationally feasible exact solution. A heuristic approach described, based on recent work leads practical method. Algorithms are described for generating starting networks, producing local improvements in testing networks each stage. locally optimum respect transformation. Randomizing solution ensures space widely sampled. Two theorems allow great reduction amount computation required test network. Finally, some examples given.