Parallel Shortcutting of Rooted Trees
Parallel Shortcutting of Rooted Trees
复制标题
有根树的并行捷径
DOI：
10.1006/jagm.1996.0829
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
M. Thorup
中科院分区：
文献类型：
--
作者：
M. Thorup
首先，表明对于任何有根的treetWithNvertices和参数？ （m，n）。被分配给弧线。 （m，n））顺序的时间。并行化。
First it is shown that for any rooted treeTwithnvertices, and parameterm?n, there is a “shortcutting” setSof at mostmarcs from the transitive closureT* ofTsuch for any (v,w)?T*, there is a dipath inT?Sfromvtowof lengthO(?(m,n)). An equivalent result has been achieved by7, but our proof is algorithmically simpler, and, in particular, it lends itself well to parallelization. More precisely, suppose that weights from a semigroup are assigned to the arcs ofT. Then we can preprocessTin timeO(logn) withO(m/logn) processors on a CREW PRAM such that for any (v,w)?T*, we can find the weight of the path fromvtowinO(?(m,n)) sequential time.2have claimed that such a parallelization is possible for Chazelle's result. This claim is used in the optimal parallel sensitivity analysis for minimum spanning trees by11. However, Alon and Schieber did not give the details of the parallelization. Here we present a full proof, and our algorithms, both the sequential and the parallel versions, are rather simple, hence likely to be of practical relevance.