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 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.