• Mar 31, 2016 News!JACN Vol.3, No.3 has been indexed by EI (inspec)!   [Click]
  • Jun 24, 2016 News!JACN Vol.4, No.2 has been published with online version. 15 papres about advances in computer networks are published in this issue.   [Click]
  • Mar 31, 2016 News!JACN Vol.3, No.2 has been indexed by EI (inspec)!   [Click]
General Information
    • ISSN: 1793-8244
    • Frequency: Quarterly
    • DOI: 10.18178/JACN
    • Editor-in-Chief: Dr. Ka Wai Gary Wong
    • Executive Editor: Ms. Julia S. Ma
    • Abstracting/ Indexing: EI (INSPEC, IET), Engineering & Technology Digital Library, DOAJ, Electronic Journals Library, Ulrich's Periodicals Directory, International Computer Science Digital Library (ICSDL), ProQuest, and Google Scholar.
    • E-mail: jacn@ejournal.net
Dr. Ka Wai Gary Wong
Department of Mathematics and Information Technology The Hong Kong Institute of Education, Hong Kong
It's a honor to serve as the editor-in-chief of JACN. I'll work together with the editors and reviewers to help the journal progress
JACN 2013 Vol.1(4): 286-290 ISSN: 1793-8244
DOI: 10.7763/JACN.2013.V1.57

Dynamic Programming for Minimal Cost Topology with Reliability Constraint

Basima Elshqeirat, Sieteng Soh, Suresh Rai, and Mihai Lazarescu
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).


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.

Copyright © 2008-2016. Journal of Advances in Computer Networks.  All rights reserved.
E-mail: jacn@ejournal.net