Efficient algorithms for centers and medians in interval and circular-arc graphsAbstract: The p-center problem is to locate p facilities on a network so as to minimize the largest distance from a demand point to its nearest facility. The p-median problem is to locate p facilities on a network so as to minimize the average distance from one of the n demand points to one of the p facilities. We consider these problems when the network can be modelled by an interval or circular-arc graph. We provide, given the interval model of an n vertex interval graph, an O(n) time algorithm for the 1-median problem on the interval graph. We also show how to solve the p-median problem, for arbitrary p, on an interval graph in O(pn log n) time and on an circular-arc graph in O(pn2 log n) time. We introduce a spring model of the objective function and show how to solve the p-center problem on an circular-arc graph in O(pn) time, assuming that the arc endpoints are sorted.
@article{bbkks-eacm-02
, author = "S. Bespamyatnikh and B. Bhattacharya and M. Keil and D. Kirkpatrick and M. Segal"
, title = "Efficient algorithms for centers and medians in interval and circular-arc graphs"
, journal = "Networks"
, volume = 33
, number = 3
, year = 2002
, pages = "144-152"
}
|