ملخص
We present approximation algorithms and structural results for problems in network design. We give improved approximation algorithms for finding rain-cost k-outconnected graphs with either a single root or multiple roots for (i) uniform costs, and (ii) metric costs. The improvements are obtained by focusing on single-root k-outcormected graphs and proving (i) a version of Mader’s critical cycle theorem and (ii) an extension of a splitting off theorem by Bienstock et al.
اللغة الأصلية | الإنجليزيّة |
---|---|
عنوان منشور المضيف | Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings |
المحررون | José Rolim, Klaus Jansen |
ناشر | Springer Verlag |
الصفحات | 77-88 |
عدد الصفحات | 12 |
رقم المعيار الدولي للكتب (المطبوع) | 3540647368, 9783540647362 |
المعرِّفات الرقمية للأشياء | |
حالة النشر | نُشِر - 1998 |
منشور خارجيًا | نعم |
الحدث | International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 1998 - Aalborg, الدنمارك المدة: ١٨ يوليو ١٩٩٨ → ١٩ يوليو ١٩٩٨ |
سلسلة المنشورات
الاسم | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
مستوى الصوت | 1444 |
رقم المعيار الدولي للدوريات (المطبوع) | 0302-9743 |
رقم المعيار الدولي للدوريات (الإلكتروني) | 1611-3349 |
!!Conference
!!Conference | International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 1998 |
---|---|
الدولة/الإقليم | الدنمارك |
المدينة | Aalborg |
المدة | ١٨/٠٧/٩٨ → ١٩/٠٧/٩٨ |
ملاحظة ببليوغرافية
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 1998.