Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network

✍ Scribed by Biing-Feng Wang

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 128 KB
• Volume: 34
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1999.1020

✦ Synopsis

In this paper, we propose efficient parallel algorithms on the EREW PRAM for optimally locating in a tree network a path-shaped facility and a tree-shaped facility of a specified length. Edges in the tree network have arbitrary positive lengths. Two optimization criteria are considered: minimum eccentricity and minimum distancesum. Let n be the number of vertices in the tree 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 for finding a minimum Ž . Ž 2 . distancesum location of a path-shaped facility takes O log n time using O n work. Both of our algorithms for finding the minimum eccentricity location and a Ž . minimum distancesum location of a tree-shaped 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 all the four problems considered in this paper. They assumed that each edge in 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 eccentricity location of a tree-shaped facility, and a minimum distancesum location of a tree-shaped facility are more efficient from the aspect of work. Ž . Ž . Their algorithms for these three problems use O n log n work. Ours use O n work.