Minimum cost source location problem with vertex-connectivity requirementsin digraphs

Given a digraph (or an undirected graph) G = (V, E) with a set V of vertice s v with nonnegative real costs w(v), and a set E of edges and a positive i nteger k, we deal with the problem of finding a minimum cost subset S subse t of or equal to V such that, for each vertex v epsilon V - S, there are k vertex-disjoint paths from S to v. In this paper, we show that the problem can be solved by a greedy algorithm in O(min{k.rootn}nm) time in a digraph (or in O(min(k,rootn)kn(2)) time in an undirected graph), where n = vertica l bar V vertical bar and m = vertical bar E vertical bar. Based on this, gi ven a digraph and two integers k and l, we also give a polynomial time algo rithm for finding a minimum cost subset S subset of or equal to V such that for each vertex V E V - S, there are k vertex-disjoint paths from S to v a s well as e vertex-disjoint paths from v to S. (C) 2001 Elsevier Science B. V. All rights reserved.