An $O(n\log n)$-Time Algorithm for the k-Center Problem in Trees

Haitao Wang, Jingru Zhang

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…