ON LOCATING PATH-SHAPED OR TREE-SHAPED FACILITIES ON NETWORKS

The study of ''optimally'' locating on a network a single facility of a given total length in the form of a path or a tree was initiated by several authors. We extend these results to the problem of locating p (greater-than-or-equal-to 1) such facilities. We will consider ''cente r'', ''median'', ''max eccentricity'', and ''max distance sum'' locati on type problems for p = 1 or p > 1, for general networks and for tree networks, whether a facility contains partial arcs or not, and whethe r a facility is path-shaped or tree-shaped. These cases lead to 64 pro blems. We will determine the algorithmic complexity of virtually all t hese problems. We conclude with a result that may be viewed as a gener alization of the p-Median theorem. (C) 1993 by John Wiley & Sons, Inc.