Efficient parallel shortest-paths in digraphs with a separator decomposition
Efficient parallel shortest-paths in digraphs with a separator decomposition
复制标题
具有分隔符分解的有向图中的高效并行最短路径
DOI：
10.1145/165231.165240
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
E. Cohen
中科院分区：
文献类型：
--
作者：
E. Cohen
我们考虑了一个扩展摘要出现在“第五届ACM并行算法和架构研讨会论文集”，1993年。边权为实值的有向图上的最短路径和可达性问题。对于稀疏图，用于这些问题的已知nnn算法比它们的顺序对应物执行更多的工作。在本文中，我们提出了图族的高效并行算法，其中分隔符分解要么提供了输入，要么很容易获得。(分隔符是顶点的子集，它的移除将图分割成连接的组件，使得每个组件中的顶点数量最多是图中顶点数量的固定分数。分隔符分解是使用分隔符的图的递归分解。LetG=(V，E)，其中=|V|是一个带ak？-分隔符分解（其中带有顶点的子图的分隔符大小为0 (k?)）。我们提出了一种算法，该算法使用ingo （n3?+s(n+n2?)）计算从源到所有其他顶点的最短路径。我们算法的顺序版本也改进了之前已知的时间范围。来源的可达性可以用ingo (M（n?)+s(n+n2?)）功来计算，其中em (r)=o（r2.37）是最著名的功界forr×rmatrix乘法。该算法基于用一组o （n2?）条边对g进行增广，使得在增广图中，所有距离都可以通过大小为o （logn）的路径获得。上面的边界？=0.5适用于平面图，因为在这些边界内可以计算ak0.5分隔符分解。对于所有顶点都位于少数面上的平面嵌入图，我们得到了进一步的改进。
We consider111An extended abstract appeared in “Proceedings 5th Annual ACM Symposium on Parallel Algorithms and Architectures”, 1993.shortest-paths and reachability problems on directed graphs with real-valued edge weights. For sparser graphs, the knownNCalgorithms 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.) LetG=(V,E), wheren=|V|, be a weighted directed graph with ak?-separator decomposition (where subgraphs withkvertices have separators of sizeO(k?)). We present anNCalgorithm that computes shortest-paths fromssources to all other vertices usingO(n3?+s(n+n2?)) work. A sequential version of our algorithm improves over previously known time bounds as well. Reachability fromssources can be computed usingO(M(n?)+s(n+n2?)) work, whereM(r)=o(r2.37) is the best known work bound forr×rmatrix multiplication. The algorithm is based on augmentingGwith a set ofO(n2?) edges such that in the augmented graph, all distances can be obtained by paths of sizeO(logn). The above bounds, with ?=0.5, are applicable to planar graphs, since ak0.5-separator decomposition can be computed within these bounds. We obtain further improvements for graphs with planar embeddings where all vertices lie on a small number of faces.