On rooted node-connectivity problems

J. Cheriyan, T. Jordan, Z. Nutov

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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.

שפה מקוריתאנגלית
עמודים (מ-עד)353-375
מספר עמודים23
כתב עתAlgorithmica
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - יולי 2001

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On rooted node-connectivity problems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי