A Subquadratic Time Algorithm for the Weighted k-Center Problem on Cactus Graphs
摘要
The weighted k-center problem in graphs is a classical facility location problem where we place k centers on the graph, which minimize the maximum weighted distance of a vertex to its nearest center. We study this problem when the underlying graph is a cactus with n vertices and present an \(O(n \log ^2 n)\) time algorithm for the same. This time complexity improves upon the \(O(n^2)\) time algorithm by Ben-Moshe et al. [2], which is the current state-of-the-art.