We consider a classical k-center problem in trees. Let T be a tree of n vertices and every vertex has a nonnegative weight. The problem is to find k centers on the edges of T such that the maximum weighted distance from all vertices to their closest centers is minimized. Megiddo and Tamir (SIAM J. Comput., 1983) gave an algorithm that can solve the problem in @math time by using Cole's parametric search. Since then it has been open for over three decades whether the problem can be solved in @math time. In this paper, we present an @math time algorithm for the problem and thus settle the open problem affirmatively.
For the unweighted case where the vertices of @math have the same weight, an @math -time algorithm was given in @cite_29 for the @math -center problem. Later, @cite_26 solved the problem in @math time, and the algorithm was improved to @math time @cite_16 . Finally, Frederickson @cite_10 solved the problem in @math time. The above four papers also solve the discrete case and the following problem version in the same running times: All points of @math are considered as demand points and the centers are required to be at vertices of @math . Further, if all points of @math are demand points and centers can be any points of @math , Megiddo and Tamir solved the problem in @math time @cite_11 , and the running time can be reduced to @math by applying Cole's parametric search @cite_21 .
@cite_26 @cite_29 @cite_21 @cite_16 @cite_10 @cite_11
2141178123 1671942308 1996896896 1529668588 2032624334
Many known algorithms are based on selection in a set whose cardinality is superlinear in terms of the input length. It is desirable in these cases to have selection algorithms that run in sublinear time in terms of the cardinality of the set. This paper presents a successful development in this direction. The methods developed here are applied to improve the previously known upper bounds for the time complexity of various location problems. Megiddo introduced a technique for using a parallel algorithm for one problem to construct an efficient serial algorithm for a second problem. We give a general method that trims a factor o f 0(logn) time (or more) for many applications of this technique. A succinct and easily searchable representation of the set of intervertex distances of a tree is given. Algorithms are presented for generating this representation, for searching it to select a kth longest path, and for searching it to locate a p-center. The complete algorithm for path selection is asymptotically optimal in the worst case, and the algorithms for p-center location improve on previous methods. The p-center results are extended to networks with independent cycles. Linear-time and -space algorithms are presented for solving three versions of the p-center problem in a tree. The techniques are an application of parametric search. An @math algorithm for the continuous p-center problem on a tree is presented. Following a sequence of previous algorithms, ours is the first one whose time bound in uniform in p and less than quadratic in n. We also present an @math algorithm for a weighted discrete p-center problem.