Department of Applied Mathematics & Physics, Kyoto University

### Technical Report 2010-013 (October 28, 2010) Approximation algorithms for the source location problem with local vertex-connectivity demands by Takuro Fukunaga

The source location problem is a problem of computing a minimum cost source set in an undirected graph so that the connectivity between the source set and a vertex is at least the demand of the vertex. In this paper, we propose an O(d log d)-approximation algorithm for the problem with vertex-connectivity $\hat{\kappa}$ where d is the maximum demand. We also define another formulatin of the source location problem and propose an approximation algorithm for it.