Improved algorithms to network p-center location problems

详细信息    查看全文

• 作者：Binay Bhattacharya ; Qiaosheng Shi
• 关键词：Center problem ; Tree decomposition ; Klee始s measure problem
• 刊名：Computational Geometry
• 出版年：February, 2014
• 年：2014
• 卷：47
• 期：2_part_PC
• 页码：307-315
• 全文大小：311 K

文摘

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.