Maximum-cover source location problems with objective edge-connectivity three

Given a graph G=(V, E), a set of vertices <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${S \subseteq V}$$</EquationSource> </InlineEquation> covers a vertex <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$${v \in V}$$</EquationSource> </InlineEquation> if the edge-connectivity between S and v is at least a given number k. Vertices in S are called sources. The maximum-cover source location problem, which is a variation of the source location problem, is to find a source set S with a given size at most p, maximizing the sum of the weight of vertices covered by S. In this paper, we show a polynomial-time algorithm for this problem in the case of k = 3 for a given undirected graph with a vertex weight function and an edge capacity function. Moreover, we show that this problem is NP-hard even if vertex weights and edge capacities are both uniform for general k. Copyright Springer-Verlag 2009