On update algorithms for quickest paths

The quickest path problem deals with the transmission of a message of size cr from a source to a destination with the minimum end-to-end delay over a network with bandwidth and delay constraints on the links. The path-table t hat maps all intervals for sigma to the corresponding quickest paths can be computed in O(m(2) + mn log n) time, where n and rn are the number of node s and links of the network, respectively. We propose linear-time algorithms that update the path-table after a increase or decrease bandwidth of a lin k or a path, respectively. (C) 2000 Elsevier Science B.V. All rights reserv ed.