Show simple item record

dc.contributor.authorElshqeirat, B.
dc.contributor.authorSoh, Sieteng
dc.contributor.authorRai, S.
dc.contributor.authorLazarescu, Mihai
dc.identifier.citationElshqeirat, Basima and Soh, Sieteng and Rai, Suresh and Lazarescu, Mihai. 2013. Dynamic programming for minimal cost topology with reliability constraint. Journal of Advances in Computer Networks. 1 (4): pp. 286-290.

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.

dc.publisherIEEE Press
dc.subjectnetwork reliability
dc.subjectnetwork optimization
dc.subjectDynamic programing
dc.subjectnetwork topology design
dc.titleDynamic Programming for Minimal Cost Topology with Two Terminal Reliability Constraint
dc.typeJournal Article
dcterms.source.titleThe 19th Asia Pacific Conference on Communications
dcterms.source.seriesThe 19th Asia Pacific Conference on Communications
dcterms.source.conferenceAsia Pacific Conference on Communications 2013 (APCC2013)
dcterms.source.conference-start-dateAug 29 2013
dcterms.source.conferencelocationBali, Indonesia
dcterms.source.placeIEEE Operations Center, 445 Hoes Lane, Piscataway, NJ 08854
curtin.accessStatusFulltext not available

Files in this item


This item appears in the following Collection(s)

Show simple item record