A Subquadratic Time Algorithm for the Weighted k-Center Problem on Cactus Graphs

03/30/2023

∙

by   Binay Bhattacharya, et al.

∙

0

∙

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.