The Connected P‐Median Problem on Cactus Graphs
Authors:
Open Access
- 1 January 2021
- journal article
- research article
- Published by Wiley in Computational Intelligence and Neuroscience
- Vol. 2021 (1) , 3533623
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.Keywords
Funding Information
- Henan Agricultural University
- Natural Science Foundation of Shandong Province (ZR2021MA012)
This publication has 6 references indexed in Scilit:
- The connected p-center problem on cactus graphsTheoretical Computer Science, 2018
- The Connected p-Center Problem on Cactus Graphs2016
- Algorithms for connected p-centdian problem on block graphsJournal of Combinatorial Optimization, 2016
- The connected p-center problem on block graphs with forbidden verticesTheoretical Computer Science, 2012
- State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median ProblemsManagement Science, 1983
- Optimum Locations of Switching Centers and the Absolute Centers and Medians of a GraphOperations Research, 1964