Cost-optimal parallel algorithms for the tree bisector and related problems

An edge is a bisector of a simple path if it contains the middle point of t he path. Let T = (V, E) be a tree. Given a source vertex s is an element of V, the single-source tree bisector problem is to find, for every vertex v is an element of V, a bisector of the simple path from s to v. The all-pair s tree bisector problem is to find for, every pair of vertices u, v is an e lement of V, a bisector of the simple path from u to v. In this paper, it i s first shown that solving the single-source tree bisector problem of a wei ghted tree has a time lower bound Omega (n log n) in the sequential case. T hen, efficient parallel algorithms are proposed on the EREW PRAM for the si ngle-source and all-pairs tree bisector problems. Two O(log n) time single- source algorithms are proposed. One uses O(n) work and is for unweighted tr ees. The other uses O(n log n) work and is for weighted trees. Previous alg orithms for the single-source problem could achieve the same time O(log n) and the same optimal work, O(n) for unweighted trees and O(n log n) for wei ghted trees, on the CRCW PRAM. The contribution of our single-source algori thms is the improvement from CRCW to EREW. One all-pairs parallel algorithm is proposed. It requires O(log n) time using O(n(2)) work. All the propose d algorithms are cost-optimal. Efficient tree bisector algorithms have prac tical applications to several location problems on trees. Using the propose d algorithms, efficient parallel solutions for those problems are also pres ented.