On update algorithms for quickest paths

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

doi:10.1016/S0140-3664(00)00158-4

On update algorithms for quickest paths

Y. C. Bang, S. Radhakrishnan, N. S.V. Rao, S. G. Batsell

Autonomous and Complex Systems

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

The quickest path problem deals with the transmission of a message of size σ 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 σ to the corresponding quickest paths can be computed in O(m²+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.

Original language	English
Pages (from-to)	1064-1068
Number of pages	5
Journal	Computer Communications
Volume	23
Issue number	11
DOIs	https://doi.org/10.1016/S0140-3664(00)00158-4
State	Published - Jun 1 2000

Access to Document

10.1016/S0140-3664(00)00158-4

Cite this

@article{f55c2ce34e85430284132d4b4d971d40,

title = "On update algorithms for quickest paths",

abstract = "The quickest path problem deals with the transmission of a message of size σ 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 σ to the corresponding quickest paths can be computed in O(m2+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.",

author = "Bang, {Y. C.} and S. Radhakrishnan and Rao, {N. S.V.} and Batsell, {S. G.}",

year = "2000",

month = jun,

day = "1",

doi = "10.1016/S0140-3664(00)00158-4",

language = "English",

volume = "23",

pages = "1064--1068",

journal = "Computer Communications",

issn = "0140-3664",

publisher = "Elsevier",

number = "11",

}

TY - JOUR

T1 - On update algorithms for quickest paths

AU - Bang, Y. C.

AU - Radhakrishnan, S.

AU - Rao, N. S.V.

AU - Batsell, S. G.

PY - 2000/6/1

Y1 - 2000/6/1

N2 - The quickest path problem deals with the transmission of a message of size σ 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 σ to the corresponding quickest paths can be computed in O(m2+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.

AB - The quickest path problem deals with the transmission of a message of size σ 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 σ to the corresponding quickest paths can be computed in O(m2+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.

UR - http://www.scopus.com/inward/record.url?scp=0033740627&partnerID=8YFLogxK

U2 - 10.1016/S0140-3664(00)00158-4

DO - 10.1016/S0140-3664(00)00158-4

M3 - Article

AN - SCOPUS:0033740627

SN - 0140-3664

VL - 23

SP - 1064

EP - 1068

JO - Computer Communications

JF - Computer Communications

IS - 11

ER -

On update algorithms for quickest paths

Abstract

Access to Document

Other files and links

Fingerprint

Cite this