Multiple additively constrained path selection

G. Cheng, N. Ansari

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

Finding a feasible path subject to multiple constraints in a network is an NP-complete problem and has been extensively studied. However, current algorithms suffer either high computational complexity or low success ratio in finding feasible paths. The authors propose a novel extended Bellman-Ford algorithm (EB), from which they present a high-performance algorithm with low computational complexity in finding feasible paths with multiple additive constraints. Through analysis and simulations, it is shown that the algorithm outperforms its contenders in the success rate of finding a feasible path as well as in terms of scalability; the proposed algorithm can achieve almost 100% success ratio as long as a feasible path exists. Furthermore, the worst case computational complexity is only twice that of the Bellman-Ford algorithm.

Original languageEnglish (US)
Pages (from-to)237-241
Number of pages5
JournalIEE Proceedings: Communications
Volume149
Issue number5-6
DOIs
StatePublished - 2002

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Multiple additively constrained path selection'. Together they form a unique fingerprint.

Cite this