Parallel Shortcutting of Rooted Trees

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.