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

pdf File


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.