The Connected p-Center Problem on 3-Cactus Networks with Forbidden Nodes

Abstract

Let G(V, E, W) be a network with n-node-set V and m-link-set E, where each link e is associated with a positive distance W(e). The traditional p-Center problem is to locate some type of facilities at p nodes to minimize the maximum distance between any node and its nearest facility. This paper proposes an additional practical constraint. We restrict that the subnetwork induced by the p facility nodes must be connected. The resulting problem is called the Connected p-Center problem (the CpC problem). This paper designs an O(pn)-time algorithm for the CpC problem on 3-cactus networks using a very elegant approach. Then, we extend the algorithm to 3-cactus networks with forbidden nodes, i.e. some nodes in V cannot be selected as centers, and the complexity is still O(pn). Keywords: connected p-center, induced subnetwork, cactus network, k-cactus network, network with forbidden vertices