2016/04/26 by Banik, Aritra, Bhattacharya, Binay, Das, Sandip +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1604.07535
We present two improved algorithms for weighted discrete p-center problem for tree networks with n vertices. One of our proposed algorithms runs in O(n log n + p log2 n log(n/p)) time. For all values of p, our algorithm thus runs as fast as or faster than the most efficient O(nlog2 n) time algorithm obtained by applying Cole's speed-up technique [cole1987] to the algorithm due to Megiddo and Tamir [megiddo1983], which has remained unchallenged for nearly 30 years. Our other algorithm, which is more practical, runs in O(n log n + p2 log2(n/p)) time, and when p=O(√(n)) it is faster than Megiddo and Tamir's O(n log2n loglog n) time algorithm [megiddo1983].