The source location problem with local 3-vertex-connectivity requirements Original Research Article

Let image be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex image has an integer valued demand image. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices with the minimum cardinality such that there are at least image vertex-disjoint paths between S and each vertex image. In this paper, we show that the problem with image, image can be solved in linear time. Moreover, we show that in the case where image for some vertex image, the problem is NP-hard.