The source location problem with local 3-vertex-connectivity requirements

Abstract: Let be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex has an integer valued demand . 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 vertex-disjoint paths between S and each vertex . In this paper, we show that the problem with , can be solved in linear time. Moreover, we show that in the case where for some vertex , the problem is NP-hard. [Copyright &y& Elsevier]