Location on Tree Networks: <i>P</i>-Centre and <i>n</i>-Dispersion Problems

Abstract

We consider two problems of locating facilities on trees. In the first, we wish to determine the location of n points so as to maximize the minimum distance between any pair. In the second we wish to locate p centers of a single type of facility so as to minimize the maximum distance between any point and the center nearest to it. We provide polynomial algorithms for both problems, of O(|N| 2 log n · log |N|) for the first problem and of O(|N| 2 log p) for the second, where |N| is the number of nodes in the tree.