In this paper, we consider the problem of constructing a minimum cost graph with a specified edge-connectivity under a degree constraint. For a set V of vertices, let .gif)
be a connectivity demand, a : V → ℤ+ be a lower degree bound, b : V → ℤ+ be an upper degree bound, and be a metric edge cost. The problem (V, r, a, b, c) asks to find a minimum cost multigraph G = (V, E) with no self-loops such that λ(u, v) ≥ r(u, v) holds for each vertex pair u, v ∈ V and a(v) ≤ d(v) ≤ b(v) holds for each vertex v ∈ V, where λ(u, v) (resp., d(v)) denotes the local-edge-connectivity between u and v (resp., the degree of v) in G. We reveal several conditions on functions r, a, b and c for which the above problem admits a constant-factor approximation algorithm. For example, we give a (2+2/k)-approximation algorithm to (V, r, a, b, c) with r(u, v) ≥ 2, u, v ∈ V and a uniform b(v), v ∈ V, where k = min u, v∈V r(u, v). To design the algorithms in this paper, we derive new results on splitting and detachment, which are graph transformations to split vertices into several copies of them while preserving edge-connectivity.
