An algorithm for finding the k quickest paths in a network

Y. L. Chen

doi:10.1016/0305-0548(93)90096-2

An algorithm for finding the k quickest paths in a network

Y. L. Chen

Department of Information Management

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

80 Scopus citations

Abstract

Let N be a network with n nodes and m arcs, and let σ be the amount of data to be transmitted. The quickest path problem is to find a routing path in N such that the time required to ship σ units of data from the source to the sink is minimum. The problem considered in this paper is to find the first k quickest looping paths from the source to the sink, and an algorithm with time complexity of O(m² + (m + k)n log n + k^{3 2} log k) is developed.

Original language	English
Pages (from-to)	59-65
Number of pages	7
Journal	Computers and Operations Research
Volume	20
Issue number	1
DOIs	https://doi.org/10.1016/0305-0548(93)90096-2
State	Published - Jan 1993

Access to Document

10.1016/0305-0548(93)90096-2

Cite this

@article{501a4e4cb4a948039d2b5b5f6c7de577,

title = "An algorithm for finding the k quickest paths in a network",

abstract = "Let N be a network with n nodes and m arcs, and let σ be the amount of data to be transmitted. The quickest path problem is to find a routing path in N such that the time required to ship σ units of data from the source to the sink is minimum. The problem considered in this paper is to find the first k quickest looping paths from the source to the sink, and an algorithm with time complexity of O(m2 + (m + k)n log n + k 3 2 log k) is developed.",

author = "Chen, {Y. L.}",

note = "Funding Information: ~e~nuw~ed~emenz-Thrise searchw as supported in part by the National",

year = "1993",

month = jan,

doi = "10.1016/0305-0548(93)90096-2",

language = "???core.languages.en_GB???",

volume = "20",

pages = "59--65",

journal = "Computers and Operations Research",

issn = "0305-0548",

number = "1",

}

TY - JOUR

T1 - An algorithm for finding the k quickest paths in a network

AU - Chen, Y. L.

N1 - Funding Information: ~e~nuw~ed~emenz-Thrise searchw as supported in part by the National

PY - 1993/1

Y1 - 1993/1

N2 - Let N be a network with n nodes and m arcs, and let σ be the amount of data to be transmitted. The quickest path problem is to find a routing path in N such that the time required to ship σ units of data from the source to the sink is minimum. The problem considered in this paper is to find the first k quickest looping paths from the source to the sink, and an algorithm with time complexity of O(m2 + (m + k)n log n + k 3 2 log k) is developed.

AB - Let N be a network with n nodes and m arcs, and let σ be the amount of data to be transmitted. The quickest path problem is to find a routing path in N such that the time required to ship σ units of data from the source to the sink is minimum. The problem considered in this paper is to find the first k quickest looping paths from the source to the sink, and an algorithm with time complexity of O(m2 + (m + k)n log n + k 3 2 log k) is developed.

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

U2 - 10.1016/0305-0548(93)90096-2

DO - 10.1016/0305-0548(93)90096-2

M3 - 期刊論文

AN - SCOPUS:0027264315

SN - 0305-0548

VL - 20

SP - 59

EP - 65

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 1

ER -

An algorithm for finding the k quickest paths in a network

Abstract

Access to Document

Fingerprint

Cite this