A Dynamic Programming Algorithm for Reliable Network Design
Abstract
This paper addresses an NPhard problem to design a network topology with maximum allterminal reliability subject to a cost constraint, given the locations of the various computer centers (nodes), their connecting links, each link’s reliability and cost, and the maximum budget cost to install the links. Because cost is always a major focus in network design, this problem is practical for critical applications requiring maximized reliability. This paper first formulates a Dynamic Programming (DP) scheme to solve the problem. A DP approach, called DPA1, generates the topology using all spanning trees of the network (ST_G). The paper shows that DPA1 is optimal if the spanning trees are optimally ordered. Further, the paper describes an alternative DP algorithm, called DPA2, that uses only k spanning trees (k <=n , where n = ST_G ) sorted in increasing weight and lexicographic order to improve the time efficiency of DPA1 while producing similar results. Extensive simulations using hundreds of benchmark networks that contain up to 1.899^102 spanning trees show the merits of using the sorting method, and the effectiveness of our algorithms. DPA2 is able to generate 85% optimal results, while using only a small number of k spanning trees, and up to 16.83 CPU seconds. Furthermore, the nonoptimal results are only up to 3.4% off from optimal for the simulated examples.
Citation
Source Title
ISSN
School
Collection
Related items
Showing items related by title, author, creator and subject.

Elshqeirat, Basima; Soh, Sieteng; Rai, S.; Lazarescu, M. (2015)This paper addresses an NPhard problem, referred to as Network Topology Design with minimum Cost subject to a Reliability constraint (NTDCR), to design a minimalcost communication network topology that satisfies a ...

Elshqeirat, B.; Soh, Sieteng; Rai, S.; Lazarescu, Mihai (2013)This paper addresses an NPhard problem, called NTDCR, to design a minimalcost communication network topology that satisfies a predefined reliability constraint. Since reliability is always a major issue in the network ...

Elshqeirat, B.; Soh, Sieteng; Rai, S.; Lazarescu, Mihai (2013)This paper addresses an NPhard problem, called NTDCR, to design a minimalcost communication network topology that satisfies a predefined reliability constraint. Since reliability is always a major issue in the network ...