A Subquadratic Time Algorithm for the Weighted k-Center Problem on Cactus Graphs
share
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. [TCS 2007], which is the current state-of-the-art.
READ FULL TEXT