𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Time–Work Tradeoffs of the Single-Source Shortest Paths Problem

✍ Scribed by Hanmao Shi; Thomas H Spencer

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
111 KB
Volume
30
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

We give parallel algorithms that solve the single-source shortest paths problem Ž . on a weighted, undirected graph with n vertices and m edges in O t lg n time and ŽŽ 3 2 . Ž . . Ž . Ž Ž 3 3 O n rt lg n lg nrt q m lg n work, or in O t lg n time and O n rt q . . mnrt lg n work for any t in the range lg n F t F n. These algorithms run on the EREW PRAM model. They are the first strongly polynomial exact algorithms that Ž . Ž 3 . run in o n time while doing o n work.

📜 SIMILAR VOLUMES

A Simple Parallel Algorithm for the Sing
A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs
✍ Jesper L. Träff; Christos D. Zaroliagis 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 216 KB

We present a simple parallel algorithm for the single-source shortest path problem in planar digraphs with nonnegative real edge weights. The algorithm runs on the EREW PRAM model of parallel computation in O((n 2= +n 1&= ) log n) time, performing O(n 1+= log n) work for any 0<=<1Â2. The strength of

The time-dependent shortest pair of disj
The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms
✍ Sherali, Hanif D.; Ozbay, Kaan; Subramanian, Shivaram 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB 👁 3 views

In this paper, we examine complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. Such disjoint paths address the issu