TY - JOUR

T1 - Survivable network activation problems

AU - Nutov, Zeev

N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 2013/11/25

Y1 - 2013/11/25

N2 - In the Survivable Networks Activation problem we are given a graph G=(V,E), S⊂V, a family {fuv(xu,xv):uv∈E} of monotone non-decreasing activating functions from R+2 to {0,1} each, and connectivity requirements {r(uv):uv∈R} over a set R of requirement edges on V. The goal is to find a weight assignment w={wv:v∈V} of minimum total weight w(V)=Σv∈Vwv, such that in the activated graph Gw=(V, Ew), where Ew={uv: fuv(wu,wv)=1}, the following holds: for each uv∈R, the activated graph Gw contains r(uv) pairwise edge-disjoint uv-paths such that no two of them have a node in S\-{u,v} in common. This problem was suggested recently by Panigrahi (2011) [19], generalizing the Node-Weighted Survivable Network and the Minimum-Power Survivable Network problems, as well as several other problems with motivation in wireless networks. We give new approximation algorithms for this problem. For undirected/directed graphs, our ratios are O(klogn) for k-Out/In-connected Subgraph Activation and k-Connected Subgraph Activation. For directed graphs this solves a question from Panigrahi (2011) [19] for k=1, while for the min-power case and k arbitrary this solves a question from Nutov (2010) [16]. For other versions on undirected graphs, our ratios match the best known ones for the Node-Weighted Survivable Network problem (Nutov, 2009 [14]).

AB - In the Survivable Networks Activation problem we are given a graph G=(V,E), S⊂V, a family {fuv(xu,xv):uv∈E} of monotone non-decreasing activating functions from R+2 to {0,1} each, and connectivity requirements {r(uv):uv∈R} over a set R of requirement edges on V. The goal is to find a weight assignment w={wv:v∈V} of minimum total weight w(V)=Σv∈Vwv, such that in the activated graph Gw=(V, Ew), where Ew={uv: fuv(wu,wv)=1}, the following holds: for each uv∈R, the activated graph Gw contains r(uv) pairwise edge-disjoint uv-paths such that no two of them have a node in S\-{u,v} in common. This problem was suggested recently by Panigrahi (2011) [19], generalizing the Node-Weighted Survivable Network and the Minimum-Power Survivable Network problems, as well as several other problems with motivation in wireless networks. We give new approximation algorithms for this problem. For undirected/directed graphs, our ratios are O(klogn) for k-Out/In-connected Subgraph Activation and k-Connected Subgraph Activation. For directed graphs this solves a question from Panigrahi (2011) [19] for k=1, while for the min-power case and k arbitrary this solves a question from Nutov (2010) [16]. For other versions on undirected graphs, our ratios match the best known ones for the Node-Weighted Survivable Network problem (Nutov, 2009 [14]).

KW - Approximation algorithms

KW - Graph-connectivity

KW - Network design

KW - Wireless networks

UR - http://www.scopus.com/inward/record.url?scp=84889660017&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2012.10.054

DO - 10.1016/j.tcs.2012.10.054

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:84889660017

SN - 0304-3975

VL - 514

SP - 105

EP - 115

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -