Finding All Hops k-Shortest Paths

Gang Cheng, Nirwan Ansari

Research output: Contribution to conferencePaperpeer-review

6 Scopus citations

Abstract

In this paper, we introduce and investigate a new problem referred to as the All Hops k-shortest Paths (AHKP) problem. An efficient solution, the All Hops k-shortest Paths Extended Bellman-Ford (AHKPEB) algorithm, is proposed. Especially, when k = 1, AHKPEB is an optimal comparison-based solution to the All Hops Optimal Path (AHOP) problem in terms of the worst-case computational complexity, i.e., it is impossible to find another comparison-based solution to Add-AHOP having the worst-case computational complexity lower than that of AHKPEB.

Original languageEnglish (US)
Pages474-477
Number of pages4
StatePublished - Nov 7 2003
Event2003 IEEE Pacific Rim Conference on Communications Computers and Signal Processing (PACRIM 2003) - Victoria, B.C., Canada
Duration: Aug 28 2003Aug 30 2003

Other

Other2003 IEEE Pacific Rim Conference on Communications Computers and Signal Processing (PACRIM 2003)
CountryCanada
CityVictoria, B.C.
Period8/28/038/30/03

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Networks and Communications

Keywords

  • All Hops k-shortest Paths Problem (AHKP)
  • Bellman-Ford algorithm
  • Quality of Service (QoS)

Fingerprint Dive into the research topics of 'Finding All Hops k-Shortest Paths'. Together they form a unique fingerprint.

Cite this