APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS( the 50th Anniversary of the Operations Research Society of Japan)
Takuro Fukunaga, Hiroshi Nagamochi · Journal of the Operations Research Society of Japan · 2007
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 r: (V2)→Z_+ be a connectivity demand, a: V→Z_+ be a lower degree bound, b: V→Z_+ be an upper degree bound, and c: (V2)→Q_+ 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_ 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.