Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition
✍ Scribed by Edith Cohen
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 297 KB
- Volume
- 21
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
We consider 1 shortest-paths and reachability problems on directed graphs with real-valued edge weights. For sparser graphs, the known N N C C algorithms for these problems perform much more work than their sequential counterparts. In this paper we present efficient parallel algorithms for families of graphs, where a separator decomposition either is provided with the input or is easily obtainable. ŽA separator is a subset of the vertices that its removal splits the graph into connected components, such that the number of vertices in each component is at most a fixed fraction of the number of vertices in the graph. A separator . decomposition is a recursive decomposition of the graph using separators. Let Ž .
< <
Gs V, E , where n s V , be a weighted directed graph with a k -separator Ž Ž .. decomposition where subgraphs with k vertices have separators of size O k . We present an N N C C algorithm that computes shortest-paths from s sources to all ˜3 2 Ž Ž . . other vertices using O n q s n q n work. A sequential version of our algorithm improves over previously known time bounds as well. Reachability from