—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
—Dynamic programing, network optimization,
network reliability, network topology design.
B. Elshqeirat, S. Soh, and M. Lazarescu are with Department of
Computing, Curtin University, Perth, Western Australia; (e-mail:
M.Lazarescu@curtin.edu.au; tel.: +61 8 9266 2984; fax: +61 8 9266 2819).
S. Rai is with Department of Electrical and Computer Engineering,
Louisiana State University, Baton Rouge, LA, USA. (e-mail: firstname.lastname@example.org).
Cite:Basima Elshqeirat, Sieteng Soh, Suresh Rai, and Mihai Lazarescu, "Dynamic Programming for Minimal Cost Topology with Reliability Constraint," Journal of Advances in Computer Networks vol. 1, no. 4, pp. 286-290, 2013.