A note on Bertsekas' small-label-first strategy

Zhi Long Chen, Warren Buckler Powell

Research output: Contribution to journalArticlepeer-review

Abstract

An example is presented to show that the worst-case complexity of Bertsekas' small-label-first strategy for the shortest path problem is exponential. It becomes polynomial if, when scanning a node i, its successors j ∈ Γ(i) are examined in the nondecreasing order of dij, the distance between i and j.

Original languageEnglish (US)
Pages (from-to)111-116
Number of pages6
JournalNetworks
Volume29
Issue number2
DOIs
StatePublished - Mar 1997

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • Labeling algorithm
  • Shortest path problem
  • Worst-case complexity

Fingerprint Dive into the research topics of 'A note on Bertsekas' small-label-first strategy'. Together they form a unique fingerprint.

Cite this