Parallel Shortcutting of Rooted Trees

✍ Scribed by Mikkel Thorup

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 305 KB
• Volume: 23
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0829

✦ Synopsis

First it is shown that for any rooted tree T with n vertices, and parameter m G n, there is a ''shortcutting'' set S of at most m arcs from the transitive closure Ž . T* of T such for any ¨, w g T *, there is a dipath in T j S from ¨to w of length Ž Ž .. Ž O ␣ m, n . An equivalent result has been achieved by Chazelle Algorithmica 2 Ž . . 1987 , 337᎐361 , 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 of T. Then we can preprocess T in time Ž . Ž . Olog n with O mrlog n processors on a CREW PRAM such that for any Ž . Ž Ž .. ¨,w gT*, we can find the weight of the path from ¨to w in O ␣ m, n Ž sequential time. Alon and Schieber ''Optimal Preprocessing for Answering On-. Line Product Queries,'' Technical Report 71r87, Tel Aviv University, 1987 have 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 by Ž Dixon ''Minimum Spanning Tree Verification, Fast Priority Queues, and Mas-. sively Parallel Factoring,'' Ph.D. thesis, Princeton University, 1993 . 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.