Given a graph H = (U,E) and connectivity requirements r = {r(u,v) : u,v ∈ R {is contained in} U}, we say that H satisfies r if it contains r(u, v) pairwise internally-disjoint wu-paths for all u, v ∈R. We consider the Survivable Network with Minimum Number of Steiner Points (SN-MSP) problem: given a finite set V of points in a normed space (M, ||·|), and connectivity requirements, find a minimum size set S C M - V of additional points, such that the unit disc graph induced by V U S satisfies the requirements. In the (node-connectivity version of the) Survivable Network Design Problem (SNDP) we are given a graph G = (V, E) with edge costs and connectivity requirements, and seek a min-cost subgraph H of G that satisfies the requirements. Let k = max r(u, v)(u,v∈ V) denote the maximum connectivity requirement. We will show a natural transformation of an SN-MSP instance (V,r) into an SNDP instance (G = (V, E),c, r), such that an α-approximation for the SNDP instance implies an α·O(k~2)-approximation algorithm for the SN-MSP instance. In particular, for the most interesting case of uniform requirement r(u, v) = k for all u, v ∈ V, we obtain for SN-MSP the ratio O{k~2 ln k), which solves an open problem from [3].
展开▼
