TY - JOUR
T1 - Approximating minimum-cost connectivity problems via uncrossable bifamilies
AU - Nutov, Zeev
N1 - Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 2012/12
Y1 - 2012/12
N2 - We give approximation algorithms for the Survivable Network problem. The input consists of a graph G = (V, E) with edge/node-costs, a node subset S ⊆ V, and connectivity requirements {r(s, t) : s, t ∈ T ⊆ V}. The goal is to find a minimum cost subgraph H of G that for all s, t ∈ T contains r(s, t) pairwise edge-disjoint st-paths such that no two of them have a node in S \ {s, t} in common. Three extensively studied particular cases are: Edge-Connectivity Survivable Network (S = ∅), Node-Connectivity Survivable Network (S = V), and Element-Connectivity Survivable Network (r(s, t) = 0 whenever s ∈ S or t ∈ S). Let k = maxs,t∈T r(s, t). In Rooted Survivable Network, there is s ∈ T such that r(u, t) = 0 for all u ε= s, and in the Subset k-Connected Subgraph problem r(s, t) = k for all s, t ∈ T.
AB - We give approximation algorithms for the Survivable Network problem. The input consists of a graph G = (V, E) with edge/node-costs, a node subset S ⊆ V, and connectivity requirements {r(s, t) : s, t ∈ T ⊆ V}. The goal is to find a minimum cost subgraph H of G that for all s, t ∈ T contains r(s, t) pairwise edge-disjoint st-paths such that no two of them have a node in S \ {s, t} in common. Three extensively studied particular cases are: Edge-Connectivity Survivable Network (S = ∅), Node-Connectivity Survivable Network (S = V), and Element-Connectivity Survivable Network (r(s, t) = 0 whenever s ∈ S or t ∈ S). Let k = maxs,t∈T r(s, t). In Rooted Survivable Network, there is s ∈ T such that r(u, t) = 0 for all u ε= s, and in the Subset k-Connected Subgraph problem r(s, t) = k for all s, t ∈ T.
UR - http://www.scopus.com/inward/record.url?scp=84872462374&partnerID=8YFLogxK
U2 - 10.1145/2390176.2390177
DO - 10.1145/2390176.2390177
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:84872462374
SN - 1549-6325
VL - 9
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 1
M1 - 1
ER -