PARALLEL SHORT CUTTING OF ROOTED TREES

First it is shown that for any rooted tree T with n vertices, and para meter m greater than or equal to n, there is a ''shortcutting'' set S of at most m arcs from the transitive closure T of T such for any (v, w) is an element of T, there is a dipath in T boolean OR S from v to w of length O(alpha(m, n)). An equivalent result has been achieved by Chazelle (Algorithmica 2 (1987), 337-361), but our proof is algorithm ically simpler, and, in particular, it lends itself well to paralleliz ation. More precisely, suppose that weights from a semigroup are assig ned to the area of T. Then we can preprocess T in time O(log n) with O (m/log n) processors on a CREW PRAM such that for any (u, w) is an ele ment of T, we can find the weight of the path from u to w in O(cu(m,n )) sequential time. Alon and Schieber (''Optimal Preprocessing for Ans wering On-Line Product Queries,'' Technical Report 71/87, Tel Aviv Uni versity, 1987) have claimed that such a parallelization is possible fo r Chazelle's result. This claim is used in the optimal parallel sensit ivity analysis for minimum spanning trees by Dixon (''Minimum Spanning Tree Verification, Fast Priority Queues, and Massively Parallel Facto ring,'' Ph.D. thesis, Princeton University,; 1993). However, Alon and Schieber did not give the details of the parallelization. Here we pres ent a full proof and our algorithms, both the sequential and the paral lel versions, are rather simple, hence likely to be of practical relev ance. (C) 1997 Academic Press.