On update algorithms for quickest paths

✍ Scribed by Y.C Bang; S Radhakrishnan; N.S.V Rao; S.G Batsell

• Book ID: 104273532
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 116 KB
• Volume: 23
• Category: Article
• ISSN: 0140-3664
• DOI: 10.1016/s0140-3664(00)00158-4

✦ Synopsis

The quickest path problem deals with the transmission of a message of size s 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 s to the corresponding quickest paths can be computed in Om 2 ϩ mn log n time, where n and m 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.