The quickest path problem

Y. L. Chen, Y. H. Chin

研究成果: 雜誌貢獻期刊論文同行評審

221 引文 斯高帕斯(Scopus)

摘要

Let N be an input network and σ 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. When the value of σ is given, an O(m2 + nm log m) algorithm is designed to find the quickest path, where m and n are the numbers of arcs and nodes in the network N, respectively. By generalizing this algorithm properly, a more general algorithm with similar time complexity is developed to find quickest paths for all possible values of σ. Using the algorithm, the values of σ can be divided into O(m) ordered regions such that each region has a corresponding quickest path; therefore, if the general algorithm is used as a preprocessing step to handle the input network N, then the problem of finding a quickest path for a given value of σ can be solved in time O(log m).

原文???core.languages.en_GB???
頁(從 - 到)153-161
頁數9
期刊Computers and Operations Research
17
發行號2
DOIs
出版狀態已出版 - 1990

指紋

深入研究「The quickest path problem」主題。共同形成了獨特的指紋。

引用此