A note on Bertsekas' small-label-first strategy

Zhi Long Chen; Warren Buckler Powell

doi:10.1002/(SICI)1097-0037(199703)29:2<111::AID-NET5>3.0.CO;2-M

A note on Bertsekas' small-label-first strategy

Zhi Long Chen
, Warren Buckler Powell

Research output: Contribution to journal › Article › peer-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 d_ij, the distance between i and j.

Original language	English (US)
Pages (from-to)	111-116
Number of pages	6
Journal	Networks
Volume	29
Issue number	2
DOIs	https://doi.org/10.1002/(SICI)1097-0037(199703)29:2<111::AID-NET5>3.0.CO;2-M
State	Published - Mar 1997

All Science Journal Classification (ASJC) codes

Information Systems
Computer Networks and Communications

Keywords

Labeling algorithm
Shortest path problem
Worst-case complexity

Access to Document

10.1002/(SICI)1097-0037(199703)29:2<111::AID-NET5>3.0.CO;2-M

Cite this

@article{76753227cbd84cbd9db028f7bc928b9a,

title = "A note on Bertsekas' small-label-first strategy",

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.",

keywords = "Labeling algorithm, Shortest path problem, Worst-case complexity",

author = "Chen, \{Zhi Long\} and Powell, \{Warren Buckler\}",

year = "1997",

month = mar,

doi = "10.1002/(SICI)1097-0037(199703)29:2<111::AID-NET5>3.0.CO;2-M",

language = "English (US)",

volume = "29",

pages = "111--116",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

T1 - A note on Bertsekas' small-label-first strategy

AU - Chen, Zhi Long

AU - Powell, Warren Buckler

PY - 1997/3

Y1 - 1997/3

N2 - 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.

AB - 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.

KW - Labeling algorithm

KW - Shortest path problem

KW - Worst-case complexity

UR - https://www.scopus.com/pages/publications/0040007562

UR - https://www.scopus.com/pages/publications/0040007562#tab=citedBy

U2 - 10.1002/(SICI)1097-0037(199703)29:2<111::AID-NET5>3.0.CO;2-M

DO - 10.1002/(SICI)1097-0037(199703)29:2<111::AID-NET5>3.0.CO;2-M

M3 - Article

AN - SCOPUS:0040007562

SN - 0028-3045

VL - 29

SP - 111

EP - 116

JO - Networks

JF - Networks

IS - 2

ER -

A note on Bertsekas' small-label-first strategy

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this