An algorithm for the quickest path problem. (English) Zbl 0881.90124
Summary: The quickest path problem arises when transmitting a given amount of data between two given nodes of a network, a lead time and a capacity (per unit of time) being assigned to each are in the network. In this paper, the problem is regarded as a bicriteria path problem, allowing the use of a very efficient algorithm which solves the quickest path problem for all possible values of the amount of data that has to be transmitted.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 90B18 | Communication networks in operations research |
Keywords:
nondominated path; path capacity; path distance; network; quickest path problem; bicriteria path problemReferences:
| [1] | Chen, Y. L.; Chin, Y. H., The quickest path problem, Comput. Oper. Res., 17, 153-161 (1990) · Zbl 0698.90083 |
| [2] | Dijkstra, E., A note on two problems in connection with graphs, Numer. Math., 1, 395-412 (1959) |
| [3] | Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, J. Assoc. Comput. Mach., 34, 596-615 (1987) · Zbl 1412.68048 |
| [4] | Hansen, P., Bicriterion path problems, (Fandel, G.; Gal, T., Multiple Criteria Decision Making: Theory and Applications. Multiple Criteria Decision Making: Theory and Applications, Lectures Notes in Economics and Mathematical Systems, Vol. 177 (1980), Springer: Springer Cambridge), 109-127 · Zbl 0444.90098 |
| [5] | Martins, E. Q.V., On a special class of bicriterion path problems, Eur. J. Oper. Res., 17, 85-94 (1984) · Zbl 0538.90086 |
| [6] | Moore, M. H., On the fastest route for convoy-type traffic in flowrate-constrained networks, Transport. Sci., 10, 113-124 (1976) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
