Location on Tree Networks: P-Centre and n-Dispersion Problems

Preprint
Publisher Website
Google Scholar
    • preprint
      • Published in RePEc
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. (This abstract was borrowed from another version of this item.)
All Related Versions

This publication has 0 references indexed in Scilit: