# Approximating subset k-connectivity problems

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

## ملخص

A subset T ⊆ V of terminals is k-connected to a root s in a directed/undirected graph J if J has k internally-disjoint vs-paths for every v ∈ T; T is k-connected in J if T is k-connected to every s ∈ T. We consider the Subset k-Connectivity Augmentation problem: given a graph G = (V,E) with edge/node-costs, a node subset T ⊆ V, and a subgraph J = (V,E J ) of G such that T is (k-1)-connected in J, find a minimum-cost augmenting edge-set F ⊆ E\E J such that T is k-connected in J∪F. The problem admits trivial ratio O(|T| 2). We consider the case |T| > k and prove that for directed/undirected graphs and edge/node-costs, a ρ-approximation algorithm for Rooted Subset k -Connectivity Augmentation implies the following approximation ratios for Subset k -Connectivity Augmentation: (i) b(ρ + k) + (|T|/|T|-k) 2O (log |T|/|T|-k) and (ii) ρ·O (|T|/|T|-k log k), where b = 1 for undirected graphs and b = 2 for directed graphs. The best known values of ρ on undirected graphs are min {|T|,O(k)} for edge-costs and min {|T|,O(k log|T|)} for node-costs; for directed graphs ρ = |T| for both versions. Our results imply that unless k = |T| - o(|T|), Subset k-Connectivity Augmentation admits the same ratios as the best known ones for the rooted version. This improves the ratios in [19,14].

اللغة الأصلية الإنجليزيّة Approximation and Online Algorithms - 9th International Workshop, WAOA 2011, Revised Selected Papers 9-20 12 https://doi.org/10.1007/978-3-642-29116-6_2 نُشِر - 2012 9th International Workshop on Approximation and Online Algorithms, WAOA 2011 - Saarbrucken, ألمانياالمدة: ٨ سبتمبر ٢٠١١ → ٩ سبتمبر ٢٠١١

### سلسلة المنشورات

الاسم Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7164 LNCS 0302-9743 1611-3349

### !!Conference

!!Conference 9th International Workshop on Approximation and Online Algorithms, WAOA 2011 ألمانيا Saarbrucken ٨/٠٩/١١ → ٩/٠٩/١١

## بصمة

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