An improved algorithm for the p-center problem on interval graphs with unit lengths

An improved algorithm for the p-center problem on interval graphs with unit lengths

0.00 Avg rating0 Votes
Article ID: iaor20082905
Country: United Kingdom
Volume: 34
Issue: 8
Start Page Number: 2215
End Page Number: 2222
Publication Date: Aug 2007
Journal: Computers and Operations Research
Authors: , ,
Keywords: graphs
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) 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).

Reviews

Required fields are marked *. Your email address will not be published.