THE OPTIMAL LOCATION OF A STRUCTURED FACILITY IN A TREE NETWORK

Abstract

Efficient parallel algorithms for finding an optimal path-shaped or tree-shaped facility with a specified size in a tree network are presented. Four kinds of optimization criteria are considered: minimizing/maximizing distancesum/eccentricity. There are eight cases when considering facility shapes and optimization criteria. Parallel algorithms for finding a minimum/maximum distancesum path were presented in [9]. The other six cases are studied in this paper. Two of these six cases can be solved optimally in linear Time x Processor complexity. For the problem of finding a maximum distancesum tree, the algorithm presented in this paper is the first polynomial time solution under a reasonable assumption.

KEY WORDS:

• distancesum
• eccentricity
• EREW PRAM
• Location theory
• parallel algorithm
• tree network
• tree contraction

C.R. CATEGORIES:

• F.2.2