ALGORITHMIC APPROACH TO NETWORK LOCATION PROBLEMS .2. P-MEDIANS

It is shown that the problem of finding a p-median of a network is an NP-hard problem even when the network has a simple structure (e. g. , planar graph of maximum vertex degree 3). However, results leading to efficient algorithms are presented when the network is a tree: in particular, it is first shown that a l-median of a tree is identical to its w-centroid, and obtain A. J. Goldman's O(n) algorithm for finding a 1-median of a tree out of more general considerations. Then an algorithm is presented which finds a p-median of a tree (for p greater than 1) in time O(n**2 multiplied by (times) p**2).