## Keywords (5)

Academic
Publications
Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs

# Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs,10.1016/j.jda.2009.06.003,Journal of D

Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs
 BibTex | RIS | RefWorks Download
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(NloglogN)-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∗⩽4, we give a tight analysis to show that it achieves an approximation ratio of 3. We also show the APX-hardness of the problem even restricted to d∗⩽4.
Journal: Journal of Discrete Algorithms - JDA , vol. 7, no. 4, pp. 570-578, 2009
View Publication
 The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
 ( www.sciencedirect.com ) ( dx.doi.org ) ( www.informatik.uni-trier.de )
More »

## Citation Context (1)

• ...Nagamochi [4] showed that the problem is NP-hard even if the cost is uniform and d ∗ = 4. This NP-hardness is strengthen by Ishii [6], who proved that the problem is APX-hard even if the cost is uniform and d ∗ = 4, and presented a max{d ∗ , 2d ∗ − 6}-approximation algorithm for the uniform cost...
• ...The next observation derived from Menger’s theorem is often observed in the source location problem (its proof can be found in [6] for example)...
• ...For ˆ κ-SLP, Ishii [6] also said that it is open whether the problem is approximable within a constant independent from d ∗ .F or RVSND, Nutov [13] mentioned the existence of O(d ∗ )-approximation algorithms as an...

## References (12)

### Some APX-completeness results for cubic graphs(Citations: 83)

Journal: Theoretical Computer Science - TCS , vol. 237, no. 1-2, pp. 123-134, 2000

### Locating Sources to Meet Flow Demands in Undirected Networks(Citations: 28)

Journal: Journal of Algorithms - JAL , vol. 42, no. 1, pp. 54-68, 2002

### An algorithm for source location in directed graphs(Citations: 16)

Journal: Operations Research Letters - ORL , vol. 33, no. 3, pp. 221-230, 2005

### Network Flow and Testing Graph Connectivity(Citations: 235)

Journal: Siam Journal on Computing - SIAMCOMP , vol. 4, no. 4, pp. 507-518, 1975

### Minimum cost source location problem with local 3-vertex-connectivity requirements(Citations: 3)

Journal: Theoretical Computer Science - TCS , vol. 372, no. 1, pp. 81-93, 2007
Sort by: