The Connected P‐Median Problem on Cactus Graphs

Authors:

Abstract
This study deals with the facility location problem of locating a set Vp of p facilities on a graph such that the subgraph induced by Vp is connected. We consider the connected p‐median problem on a cactus graph G whose vertices and edges have nonnegative weights. The aim of a connected p‐median problem is to minimize the sum of weighted distances from every vertex of a graph to the nearest vertex in Vp. We provide an O(n2p2) time algorithm for the connected p‐median problem, where n is the number of vertices.
Funding Information
  • Henan Agricultural University
  • Natural Science Foundation of Shandong Province (ZR2021MA012)