Application of computational geometry to network p-center location problems
Qiaosheng Shi, Binay Kumar Bhattacharya · Canadian Conference on Computational Geometry · 2008
In this note we showed that a p(‚ 2)-center location problem in general networks can be transformed to the well known Klee’s measure problem [3]. This resulted in an improved algorithm for the continuous case with running time O(m p n p=2 2 log ⁄ n logn). The previous best result for the problem is O(m p n p fi(n)logn) where fi(n) is the inverse Ackermann function [9]. When the underlying network is a partial k-tree (k flxed), by exploiting the geometry inherent in the problem we showed that the discrete p-center problem can be solved in O(pn p log k n) time.