The Connected P-Median Problem on Cactus Graphs

This study deals with the facility location problem of locating a set V(p) of p facilities on a graph such that the subgraph induced by V(p) 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 V(p). We provide an O(n(2)p(2)) time algorithm for the connected p-median problem, where n is the number of vertices.