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*log^2(n) * log(n/p)) time. For all values of p, our algorithm thus runs as fast as or faster than the most efficient O(n*log^2(n)) time algorithm obtained by applying Cole's [1987] speed-up technique  to the algorithm due to Megiddo and Tamir [1983], which has remained unchallenged for nearly 30 years.#R##N#Our other algorithm, which is more practical, runs in O(n*log(n) + p^2*log^2(n/p)) time, and when p=O(sqrt(n)) it is faster than Megiddo and Tamir's O(n*log^2(n) * log(log(n))) time algorithm [1983].
['Aritra Banik', 'Binay K. Bhattacharya', 'Sandip Das', 'Tsunehiko Kameda', 'Zhao Song']
The $p$-Center Problem in Tree Networks Revisited