Title
Quickest Paths: Parallelization And Dynamization
Abstract
Let N=(V,E,c,l) be a network, where G=(V,E) is a directed graph (|V|=n and |E|=m), c(e)>0 is the capacity and l(e)≥0 is the lead time for each edge e∈E. The transmission time to send σ units of data from a given source s to a destination t using path p is T(σ,p) = l(p) + σ/c(p), where l(p) is the sum of the lead times of the edges in p, and c(p) is the minimum capacity of the edges in p. The quickest path problem is to find a path of minimum transmission time to transmit the σ units of data from s to t. The problem has applications to fast data transmissions in communication networks. We present parallel algorithms for solving the quickest path problem in the case where the network is sparse [i.e. m=O(n)]. We also give algorithms for solving the dynamic quickest path problem. In this problem, the network, the lead times and the capacities on its edges, as well as the amount of data to be transmitted, change over time. The goal is to build a data structure so that one can very quickly compute the quickest path to transmit a given amount of data from any node s to any node t and also, after a dynamic change (edge lead time or edge capacity modification, or edge deletion) on the input network, to be able to update the data structure in an appropriately short time. Furthermore, we improve upon the best sequential result for the single pair quickest path problem which needs O(rm+rn log n) time, where r is the number of distinct edge capacities.
Publication Date
1-1-1995
Publication Title
Proceedings of the Annual Hawaii International Conference on System Sciences
Volume
2
Number of Pages
39-40
Document Type
Article; Proceedings Paper
Personal Identifier
scopus
DOI Link
https://doi.org/10.1109/HICSS.1995.375479
Copyright Status
Unknown
Socpus ID
85062589318 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/85062589318
STARS Citation
Kagaris, D.; Tragoudas, S.; and Pantziou, G. E., "Quickest Paths: Parallelization And Dynamization" (1995). Scopus Export 1990s. 1691.
https://stars.library.ucf.edu/scopus1990/1691