Dynamic Programming for Minimal Cost Topology with Two Terminal Reliability Constraint
This paper addresses an NP-hard problem, called NTD-CR, to design a minimal-cost communication network topology that satisfies a pre-defined reliability constraint. Since reliability is always a major issue in the network design, the problem is practical for critical applications requiring minimized...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Published: |
IEEE Press
2013
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/5718 |
| _version_ | 1848744875054333952 |
|---|---|
| author | Elshqeirat, B. Soh, Sieteng Rai, S. Lazarescu, Mihai |
| author2 | IEEE |
| author_facet | IEEE Elshqeirat, B. Soh, Sieteng Rai, S. Lazarescu, Mihai |
| author_sort | Elshqeirat, B. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | This paper addresses an NP-hard problem, called NTD-CR, to design a minimal-cost communication network topology that satisfies a pre-defined reliability constraint. Since reliability is always a major issue in the network design, the problem is practical for critical applications requiring minimized cost. The paper formulates a dynamic programming (DP) scheme to solve NTD-CR problem. DP approach, called DPCR-ST, generates the topology using a selected set of spanning trees of the network, STXmin. We propose three greedy heuristics to generate and order only k spanning trees of the network. Each heuristic allows DPCR-ST to enumerate STXmin using only k spanning trees, which improves the time complexity while producing near optimal topology. Simulations based on fully connected networks that contain up to 2.3×109 spanning trees show the merits of ordering methods and the effectiveness of our algorithm vis-à-vis four existing state-of-the-art techniques; DPCR-ST produces 81.5% optimal results, while using only 0.77% of the spanning trees contained in network. |
| first_indexed | 2025-11-14T06:08:24Z |
| format | Journal Article |
| id | curtin-20.500.11937-5718 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T06:08:24Z |
| publishDate | 2013 |
| publisher | IEEE Press |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-57182017-09-13T14:39:15Z Dynamic Programming for Minimal Cost Topology with Two Terminal Reliability Constraint Elshqeirat, B. Soh, Sieteng Rai, S. Lazarescu, Mihai IEEE network reliability network optimization Dynamic programing network topology design This paper addresses an NP-hard problem, called NTD-CR, to design a minimal-cost communication network topology that satisfies a pre-defined reliability constraint. Since reliability is always a major issue in the network design, the problem is practical for critical applications requiring minimized cost. The paper formulates a dynamic programming (DP) scheme to solve NTD-CR problem. DP approach, called DPCR-ST, generates the topology using a selected set of spanning trees of the network, STXmin. We propose three greedy heuristics to generate and order only k spanning trees of the network. Each heuristic allows DPCR-ST to enumerate STXmin using only k spanning trees, which improves the time complexity while producing near optimal topology. Simulations based on fully connected networks that contain up to 2.3×109 spanning trees show the merits of ordering methods and the effectiveness of our algorithm vis-à-vis four existing state-of-the-art techniques; DPCR-ST produces 81.5% optimal results, while using only 0.77% of the spanning trees contained in network. 2013 Journal Article http://hdl.handle.net/20.500.11937/5718 10.7763/JACN.2013.V1.57 IEEE Press restricted |
| spellingShingle | network reliability network optimization Dynamic programing network topology design Elshqeirat, B. Soh, Sieteng Rai, S. Lazarescu, Mihai Dynamic Programming for Minimal Cost Topology with Two Terminal Reliability Constraint |
| title | Dynamic Programming for Minimal Cost Topology with Two Terminal Reliability Constraint |
| title_full | Dynamic Programming for Minimal Cost Topology with Two Terminal Reliability Constraint |
| title_fullStr | Dynamic Programming for Minimal Cost Topology with Two Terminal Reliability Constraint |
| title_full_unstemmed | Dynamic Programming for Minimal Cost Topology with Two Terminal Reliability Constraint |
| title_short | Dynamic Programming for Minimal Cost Topology with Two Terminal Reliability Constraint |
| title_sort | dynamic programming for minimal cost topology with two terminal reliability constraint |
| topic | network reliability network optimization Dynamic programing network topology design |
| url | http://hdl.handle.net/20.500.11937/5718 |