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.