TY - JOUR
T1 - On rooted node-connectivity problems
AU - Cheriyan, J.
AU - Jordan, T.
AU - Nutov, Z.
PY - 2001/7
Y1 - 2001/7
N2 - Let G be a graph which is k-outconnected from a specified root node r, that is, G has k openly disjoint paths between r and v for every node v. We give necessary and sufficient conditions for the existence of a pair rv, rw of edges for which replacing these edges by a new edge vw gives a graph that is k-outconnected from r. This generalizes a theorem of Bienstock et al. on splitting off edges while preserving k-node-connectivity. We also prove that if C is a cycle in G such that each edge in C is critical with respect to k-outconnectivity from r, then C has a node v, distinct from r, which has degree k. This result is the rooted counterpart of a theorem due to Mader. We apply the above results to design approximation algorithms for the following problem: given a graph with nonnegative edge weights and node requirements cu for each node u, find a minimum-weight subgraph that contains max(cu, cv) openly disjoint paths between every pair of nodes u, v. For metric weights, our approximation guarantee is 3. For uniform weights, our approximation guarantee is min[2, (k + 2q-1)/k]. Here k is the maximum node requirement, and q is the number of positive node requirements.
AB - Let G be a graph which is k-outconnected from a specified root node r, that is, G has k openly disjoint paths between r and v for every node v. We give necessary and sufficient conditions for the existence of a pair rv, rw of edges for which replacing these edges by a new edge vw gives a graph that is k-outconnected from r. This generalizes a theorem of Bienstock et al. on splitting off edges while preserving k-node-connectivity. We also prove that if C is a cycle in G such that each edge in C is critical with respect to k-outconnectivity from r, then C has a node v, distinct from r, which has degree k. This result is the rooted counterpart of a theorem due to Mader. We apply the above results to design approximation algorithms for the following problem: given a graph with nonnegative edge weights and node requirements cu for each node u, find a minimum-weight subgraph that contains max(cu, cv) openly disjoint paths between every pair of nodes u, v. For metric weights, our approximation guarantee is 3. For uniform weights, our approximation guarantee is min[2, (k + 2q-1)/k]. Here k is the maximum node requirement, and q is the number of positive node requirements.
KW - Approximation algorithms
KW - Graph connectivity
KW - K-Outconnectivity
KW - Metric costs
KW - NP-hard problems
KW - Splitting-off theorems
KW - Uniform costs
KW - k-Connectivity
UR - http://www.scopus.com/inward/record.url?scp=0005269528&partnerID=8YFLogxK
U2 - 10.1007/s00453-001-0017-7
DO - 10.1007/s00453-001-0017-7
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:0005269528
SN - 0178-4617
VL - 30
SP - 353
EP - 375
JO - Algorithmica
JF - Algorithmica
IS - 3
ER -