An improved algorithm for the p-center problem on interval graphs with unit lengths ?
The p-center problem is to locate p facilities in a network of n  demand points so as to minimize the longest distance between a demand point and its nearest facility. We consider this problem by modelling the network as an interval graph whose edges all have unit lengths. We present an O(n) O ( n ) time algorithm for the problem under the assumption that the endpoints of the intervals are sorted, which improves on the existing best algorithm for the problem that has a run time of O(pn) O ( pn ) .
05c85 90c27