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

Socpus ID

85062589318 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85062589318

This document is currently not available here.

Share

COinS