Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
474245 | Computers & Operations Research | 2007 | 8 Pages |
Abstract
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).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
T.C.E. Cheng, Liying Kang, C.T. Ng,