Abstract
An edge is a bisector of a simple path if it contains the middle point of the path. Let T=(V, E) be a tree. The all-pairs tree bisector problem is to find for every pair of vertices u, v in V a bisector of the simple path from u to v. In this thesis, the all-pairs tree bisector problem is considered. We first present a simple sequential algorithm to solve the all-pairs tree bisector problem on weighted trees. The presented algorithm requires O(n^2) time. Then, we propose a cost-optimal parallel algorithm on the EREW PRAM. It requires O(log n) time using O(n^2) work. The problem of optimally locating a service facility in a network has been of considerable interest for many years. Besides being of theoretical interest, efficient algorithms for the all-pairs tree bisector problem have practical applications to several facility location problems on trees. In this thesis, using the proposed all-pairs algorithm, efficient parallel solutions on the EREW PRAM for those problems are also presented.