Approximating minimum cost multigraphs of specifled edge-connectivity under degree bounds ⁄
T. Fukunaga, Hiroshi Nagamochi · 2005
In this paper, we consider the problem of constructing a minimum cost graph with a specifled edge-connectivity under a degree constraint. For a set V of vertices, let r : i V 2 ¢ ! Z+ be a connectivity demand, a : V ! Z+ be a lower capacity, b : V ! Z+ be an upper capacity and c : i V 2 ¢ ! Q+ be a metric edge cost. The problem (V;r;a;b;c) asks to flnd a minimum cost multigraph G = (V;E) with no self-loops such that ‚(u;v) ‚ r(u;v) for each pair u;v 2 V and a(v) • d(v) • b(v) for each v 2 V , where ‚(u;v) (resp., d(v)) denotes the local-edge-connectivity between u and v (resp., the degree of v) in G. We show several conditions on functions r;a;b and c for which the above problem admits an approximation algorithm. For example, we give a (2 + 1=bk=2c)-approximation algorithm to (V;r;a;b;c) with r(u;v) ‚ 2, u;v 2 V and a uniform b(v), v 2 V , where k = minu;v2V r(u;v). To design the algorithms in this paper, we use our new results on edge-splitting and detachment, which are graph transformations to split vertices while preserving edge-connectivity.