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 that 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 nodes and links of the network, respectively. We propose linear-time algorithms that update the path-table after a increase or decrease bandwidth of a link or a path, respectively. (C) 2000 Elsevier Science B.V. All rights reserved.
quickest path delay network bandwidth dynamic algorithm