An Algorithmic Approach to Network Location Problems. II: The<i>p</i>-Medians

Abstract

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^2 \cdot p^2 )$.