Title | ||
---|---|---|
Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs |
Abstract | ||
---|---|---|
Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v@?V has a demand d(v)@?Z"+, and a cost c(v)@?R"+, where Z"+ and R"+ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices minimizing @?"v"@?"Sc(v) such that there are at least d(v) pairwise vertex-disjoint paths from S to v for each vertex v@?V-S. It is known that the problem is not approximable within a ratio of O(ln@?"v"@?"Vd(v)), unless NP has an O(N^l^o^g^l^o^g^N)-time deterministic algorithm. Also, it is known that even if every vertex has a uniform cost and d^*=4 holds, then the problem is NP-hard, where d^*=max{d(v)|v@?V}. In this paper, we consider the problem in the case where every vertex has uniform cost. We propose a simple greedy algorithm for providing a max{d^*,2d^*-6}-approximate solution to the problem in O(min{d^*,|V|}d^*|V|^2) time, while we also show that there exists an instance for which it provides no better than a (d^*-1)-approximate solution. Especially, in the case of d^*= |
Year | DOI | Venue |
---|---|---|
2009 | 10.1016/j.jda.2009.06.003 | J. Discrete Algorithms |
Keywords | Field | DocType |
set v,greedy approximation,location problem,vertex-connectivity requirement,graph algorithm,undirected graph,nonnegative real,source location problem,vertex v,approximate solution,simple greedy algorithm,graph g,vertex-connectivity,nonnegative integer,greedy algorithm,uniform cost,set e | Integer,Log-log plot,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Neighbourhood (graph theory),Greedy algorithm,Vertex cover,Deterministic algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
7 | 4 | Journal of Discrete Algorithms |
Citations | PageRank | References |
3 | 0.47 | 11 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Toshimasa Ishii | 1 | 110 | 17.03 |