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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 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

!!Conference9th International Workshop on Approximation and Online Algorithms, WAOA 2011
الدولة/الإقليمألمانيا
المدينةSaarbrucken
المدة٨/٠٩/١١٩/٠٩/١١

بصمة

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

قم بذكر هذا