Efficient parallel algorithms for optimally locating a path and a tree of a specified length in a weighted tree network

In this paper, we propose efficient parallel algorithms on the EREW PRAM fo r optimally locating in a tree network a path-shaped facility and a tree-sh aped facility of a specified length. Edges in the tree network have arbitra ry positive lengths. Two optimization criteria are considered: minimum ecce ntricity and minimum distancesum. Let n be the number of vertices in the tr ee network. Our algorithm for finding a minimum eccentricity location of a path-shaped facility takes O(log n) time using O(n) work. Our algorithm far finding a minimum distancesum location of a path-shaped facility takes O(l og n) time using O(n(2)) work. Both of our algorithms for finding the minim um eccentricity location and a minimum distancesum location of a tree-shape d facility take O(log n log log n) time using O(n) work. In the sequential case, all the proposed algorithms are faster than those previously proposed by Minieka. Recently, Peng and Lo have proposed parallel algorithms for al l the four problems considered in this paper. They assumed that each edge i n the tree network is of length 1. Thus, as compared with their algorithms ours are more general. Besides, our algorithms for the problems of finding a minimum eccentricity location of a path-shaped facility, the minimum ecce ntricity location of a tree-shaped facility, and a minimum distancesum loca tion of a tree-shaped facility are more efficient from the aspect of work. Their algorithms far these three problems use O(n log n) work. Ours use O(n ) work. (C) 2000 Academic Press.