| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419623 | Discrete Applied Mathematics | 2013 | 6 Pages |
Let G=(V,E)G=(V,E) be a kk-edge-connected graph with edge-costs {c(e):e∈E}{c(e):e∈E} and minimum degree dd. We show by a simple and short proof, that for any integer ℓℓ with dk≤ℓ≤d(1−1k), GG contains an ℓℓ-edge cover II such that: c(I)≤ℓdc(E) if GG is bipartite, or if ℓ|V|ℓ|V| is even, or if |E|≥d|V|2+d2ℓ; otherwise, c(I)≤(ℓd+1d|V|)c(E). The particular case d=k=ℓ+1d=k=ℓ+1 and unit costs already includes a result of Cheriyan and Thurimella (2000) [1], that GG contains a (k−1)(k−1)-edge-cover of size |E|−⌊|V|/2⌋|E|−⌊|V|/2⌋. Using our result, we slightly improve the approximation ratios for the kk-Connected Subgraph problem (the node-connectivity version) with uniform and ββ-metric costs. We then consider the dual problem of finding a spanning subgraph of maximum connectivity k∗k∗ with a prescribed number of edges. We give an algorithm that computes a (k∗−1)(k∗−1)-connected subgraph, which is tight, since the problem is NP-hard.
