Approximating survivable networks with minimum number of steiner points

作者：Kamma Lior; Nutov Zeev^*

来源：Networks, 2012, 60(4): 245-252.

DOI：10.1002/net.21466

• sensor networks
• unit disc graphs
• node-connectivity
• approximation algorithms

Given a graph H = (U, E) and connectivity requirements r = {r(u, v) : u, v is an element of R subset of U}, we say that H satisfies r if it contains r(u, v) pairwise internally-disjoint uv-paths for all u, v is an element of 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, parallel to center dot parallel to) and connectivity requirements, find a minimum size set S subset of M \ V of additional points, such that the unit disc graph induced by U = V boolean OR S satisfies the requirements. In the (node-connectivity) Survivable Network Design Problem (SNDP) we are given a graph G = (V, E) with edge costs and connectivity requirements, and seek a minimum cost subgraph H of G that satisfies the requirements. Let k = max(u,v is an element of V) r(u, 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 alpha-approximation algorithm for the SNDP instance implies an alpha center dot O(k(2))-approximation algorithm for the SN-MSP instance. In particular, for the case of uniform requirements r(u, v) = k for all u, v is an element of V, we obtain for SN-MSP the ratio O(k(2) ln k), which solves an open problem from (Bredin et al. Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) (2005), 309319).

• 出版日期2012-12