Finding All Hops Shortest Paths

Gang Cheng; Nirwan Ansari

doi:10.1109/LCOMM.2004.823365

Finding All Hops Shortest Paths

Gang Cheng, Nirwan Ansari

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

19 Scopus citations

Abstract

In this letter, we introduce and investigate a new problem referred to as the All Hops Shortest Paths (AHSP) problem. The AHSP problem involves selecting, for all hop counts, the shortest paths from a given source to any other node in a network. We derive a tight lower bound on the worst-case computational complexities of the optimal comparison-based solutions to AHSP.

Original language	English (US)
Pages (from-to)	122-124
Number of pages	3
Journal	IEEE Communications Letters
Volume	8
Issue number	2
DOIs	https://doi.org/10.1109/LCOMM.2004.823365
State	Published - Feb 2004

All Science Journal Classification (ASJC) codes

Modeling and Simulation
Computer Science Applications
Electrical and Electronic Engineering

Keywords

Quality of service (QoS)
Routing

Access to Document

10.1109/LCOMM.2004.823365

Cite this

@article{d47032ce6206466eb990a31d566af79b,

title = "Finding All Hops Shortest Paths",

abstract = "In this letter, we introduce and investigate a new problem referred to as the All Hops Shortest Paths (AHSP) problem. The AHSP problem involves selecting, for all hop counts, the shortest paths from a given source to any other node in a network. We derive a tight lower bound on the worst-case computational complexities of the optimal comparison-based solutions to AHSP.",

keywords = "Quality of service (QoS), Routing",

author = "Gang Cheng and Nirwan Ansari",

note = "Funding Information: Manuscript received June 4, 2003. The associate editor coordinating the review of this letter and approving it for publication was Prof. M. Ma. This work has been supported in part by the New Jersey Commission on Higher Education via the NJI-TOWER project, and the New Jersey Commission on Science and Technology via NJWINS.",

year = "2004",

month = feb,

doi = "10.1109/LCOMM.2004.823365",

language = "English (US)",

volume = "8",

pages = "122--124",

journal = "IEEE Communications Letters",

issn = "1089-7798",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "2",

}

TY - JOUR

T1 - Finding All Hops Shortest Paths

AU - Cheng, Gang

AU - Ansari, Nirwan

N1 - Funding Information: Manuscript received June 4, 2003. The associate editor coordinating the review of this letter and approving it for publication was Prof. M. Ma. This work has been supported in part by the New Jersey Commission on Higher Education via the NJI-TOWER project, and the New Jersey Commission on Science and Technology via NJWINS.

PY - 2004/2

Y1 - 2004/2

N2 - In this letter, we introduce and investigate a new problem referred to as the All Hops Shortest Paths (AHSP) problem. The AHSP problem involves selecting, for all hop counts, the shortest paths from a given source to any other node in a network. We derive a tight lower bound on the worst-case computational complexities of the optimal comparison-based solutions to AHSP.

AB - In this letter, we introduce and investigate a new problem referred to as the All Hops Shortest Paths (AHSP) problem. The AHSP problem involves selecting, for all hop counts, the shortest paths from a given source to any other node in a network. We derive a tight lower bound on the worst-case computational complexities of the optimal comparison-based solutions to AHSP.

KW - Quality of service (QoS)

KW - Routing

UR - http://www.scopus.com/inward/record.url?scp=1642310478&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1642310478&partnerID=8YFLogxK

U2 - 10.1109/LCOMM.2004.823365

DO - 10.1109/LCOMM.2004.823365

M3 - Article

AN - SCOPUS:1642310478

SN - 1089-7798

VL - 8

SP - 122

EP - 124

JO - IEEE Communications Letters

JF - IEEE Communications Letters

IS - 2

ER -

Finding All Hops Shortest Paths

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this