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
مستوى الصوت30
رقم الإصدار3
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - يوليو 2001


أدرس بدقة موضوعات البحث “On rooted node-connectivity problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا