文摘
In this paper we show that a -center location problem in general networks can be transformed to the well-known Klee始s measure problem (Overmars and Yap, 1991) . This results in a significantly improved algorithm for the continuous case with running time for , where n is the number of vertices, m is the number of edges, and denotes the iterated logarithm of n (Cormen et al., 2001) . For , the running time of the improved algorithm is . The previous best result for the problem is where is the inverse Ackermann function (Tamir, 1988) . When the underlying network is a partial k-tree (k fixed), we exploit the geometry inherent in the problem and propose a two-level tree decomposition data structure which can be used to efficiently solve discrete p-center problems for small values of p.