2012 | OriginalPaper | Chapter
Survivable Network Activation Problems
Author : Zeev Nutov
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In the
Survivable Networks Activation
problem we are given a graph
G
= (
V
,
E
),
S
⊆
V
, a family {
f
uv
(
x
u
,
x
v
):
uv
∈
E
} of monotone non-decreasing
activating functions
from
$\mathbb{R}^2_+$
to {0,1} each, and
connectivity requirements
{
r
(
u
,
v
):
u
,
v
∈
V
}. The goal is to find a
weight assignment
w
= {
w
v
:
v
∈
V
} of minimum total weight
w
(
V
) = ∑
v
∈
V
w
v
, such that: for all
u
,
v
∈
V
, the
activated graph
G
w
= (
V
,
E
w
), where
E
w
= {
uv
:
f
uv
(
w
u
,
w
v
) = 1}, contains
r
(
u
,
v
) 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 [12], 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
(
k
log
n
) for
k
-Out/In-connected Subgraph Activation
and
k
-Connected Subgraph Activation
. For directed graphs this solves a question from [12] for
k
= 1, while for the min-power case and
k
arbitrary this solves an open question from [9]. For other versions on undirected graphs, our ratios match the best known ones for the
Node-Weighted Survivable Network
problem [8].