The weighted k-center problem in trees for fixed k
Binay Kumar Bhattacharya, Sandip Das, Subhadeep Ranjan Dev · Theoretical Computer Science · 2022
We present a linear time algorithm for the weighted k -center problem on trees for fixed k . This partially settles the long-standing question about the lower bound on the time complexity of the problem. The current time complexity of the best-known algorithm for the problem with k as part of the input is O ( n log n ) by Wang et al. (2018) [20] . Whether an O ( n ) time algorithm exists for arbitrary k is still open.