APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)

概要

論文の詳細を見る
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_<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.
社団法人日本オペレーションズ・リサーチ学会の論文