A Dynamic Programming Algorithm for Reliable Network Design
This paper addresses an NP-hard problem to design a network topology with maximum all-terminal 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 l...
| Main Authors: | , , , |
|---|---|
| Format: | Journal Article |
| Published: |
IEEE
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/14610 |
| _version_ | 1848748668755116032 |
|---|---|
| author | Elshqeirat, Basima Soh, Sieteng Rai, S. Lazarescu, Mihai |
| author_facet | Elshqeirat, Basima Soh, Sieteng Rai, S. Lazarescu, Mihai |
| author_sort | Elshqeirat, Basima |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | This paper addresses an NP-hard problem to design a network topology with maximum all-terminal 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 DPA-1, generates the topology using all spanning trees of the network (ST_G). The paper shows that DPA-1 is optimal if the spanning trees are optimally ordered. Further, the paper describes an alternative DP algorithm, called DPA-2, 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 DPA-1 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. DPA-2 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 non-optimal results are only up to 3.4% off from optimal for the simulated examples. |
| first_indexed | 2025-11-14T07:08:42Z |
| format | Journal Article |
| id | curtin-20.500.11937-14610 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:08:42Z |
| publishDate | 2014 |
| publisher | IEEE |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-146102017-09-13T14:06:26Z A Dynamic Programming Algorithm for Reliable Network Design Elshqeirat, Basima Soh, Sieteng Rai, S. Lazarescu, Mihai network reliability network optimisation network topology design Dynamic programming This paper addresses an NP-hard problem to design a network topology with maximum all-terminal 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 DPA-1, generates the topology using all spanning trees of the network (ST_G). The paper shows that DPA-1 is optimal if the spanning trees are optimally ordered. Further, the paper describes an alternative DP algorithm, called DPA-2, 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 DPA-1 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. DPA-2 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 non-optimal results are only up to 3.4% off from optimal for the simulated examples. 2014 Journal Article http://hdl.handle.net/20.500.11937/14610 10.1109/TR.2014.2314597 IEEE restricted |
| spellingShingle | network reliability network optimisation network topology design Dynamic programming Elshqeirat, Basima Soh, Sieteng Rai, S. Lazarescu, Mihai A Dynamic Programming Algorithm for Reliable Network Design |
| title | A Dynamic Programming Algorithm for Reliable Network Design |
| title_full | A Dynamic Programming Algorithm for Reliable Network Design |
| title_fullStr | A Dynamic Programming Algorithm for Reliable Network Design |
| title_full_unstemmed | A Dynamic Programming Algorithm for Reliable Network Design |
| title_short | A Dynamic Programming Algorithm for Reliable Network Design |
| title_sort | dynamic programming algorithm for reliable network design |
| topic | network reliability network optimisation network topology design Dynamic programming |
| url | http://hdl.handle.net/20.500.11937/14610 |