The quickest path problem

The quickest path problem

0.00 Avg rating0 Votes
Article ID: iaor19891065
Country: United Kingdom
Volume: 17
Start Page Number: 153
End Page Number: 161
Publication Date: Dec 1990
Journal: Computers and Operations Research
Authors: ,
Abstract:

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+nmlogm) 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(logm).

Reviews

Required fields are marked *. Your email address will not be published.