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

Citation
Sl. Hakimi et al., ON LOCATING PATH-SHAPED OR TREE-SHAPED FACILITIES ON NETWORKS, Networks, 23(6), 1993, pp. 543-555
Citations number
15
Categorie Soggetti
Mathematics,"Computer Sciences","Computer Applications & Cybernetics
Journal title
ISSN journal
00283045
Volume
23
Issue
6
Year of publication
1993
Pages
543 - 555
Database
ISI
SICI code
0028-3045(1993)23:6<543:OLPOTF>2.0.ZU;2-7
Abstract
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.