The connected p-center problem on block graphs with forbidden vertices
Let G(V, E, w, l) denote an n-vertex and m-edge graph in which in is a function mapping each vertex v to a positive weight w(v) and I is a function mapping each edge e to a positive length l(e). Given a positive integer p, the p-Center problem involves finding a set Q with p vertices of G to be the locations for building facilities. The objective is to minimize the maximum weighted distance from each vertex in V-Q to its nearest vertex in Q. This paper considers a practical restriction: the induced subgraph of the selected p vertices must be connected. The new variant is called the Connected p-Center problem (the CpC problem). For each fixed integer t >= 1, on block graphs with exactly t blocks, we first show that the CpC problem is NP-hard when (1) w(v) = 1, for all vertices v, and l(e) is an element of {1, 2}, for all edges e, and (2) w(v) is an element of {1, 2}, for all vertices v, and l(e) = 1, for all edges e, respectively. Second, an O(n + m)-time algorithm for solving the CpC problem on block graphs with unit vertex-weights and unit edge-lengths is proposed. Then, the algorithmic result is extended to handle the situation in which some vertices in G cannot be included to form feasible solutions. The complexity of the extended algorithm is also O(n + m). (C) 2011 Elsevier B.V. All rights reserved.
connected p-centers block graphs graphs with forbidden vertices np-hard block degrees