z-logo
Premium
Approximating survivable networks with minimum number of steiner points
Author(s) -
Kamma Lior,
Nutov Zeev
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21466
Subject(s) - combinatorics , steiner tree problem , disjoint sets , mathematics , graph , discrete mathematics , approximation algorithm , computer science
Given a graph H = ( U , E ) and connectivity requirements r = { r ( u , v ) : u , v ∈ R ⊆ U }, we say that H satisfies r if it contains r ( u , v ) pairwise internally‐disjoint uv ‐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 ⊂ M \ V of additional points, such that the unit disc graph induced by U = V ∪ 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 ∈ 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 α‐approximation algorithm for the SNDP instance implies an α · 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 ∈ 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), 309–319). © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here