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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Binay Bhattacharya,
  • Sandip Das,
  • Subhadeep Ranjan Dev

摘要

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.