Abstract—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.
Index Terms—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:
Basima.elshoqeirat@postgrad.curtin.edu.au, S.Soh@curtin.edu.au,
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: srai@lsu.edu).
[PDF]
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.