An Algorithmic Approach to Network Location Problems. II: Thep-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, we first show that a 1-median of a tree is identical to its w-centroid, and obtain Goldman’s O (n) algorithm for finding a 1-median of a tree out of more general considerations. Then, we present an algorithm which finds a p-median of a tree (for p > 1) in time O (n² p²).