Approximating k-outconnected subgraph problems

Joseph Cheriyan, Tibor Jordàn, Zeev Nutov

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

ملخص

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

!!ConferenceInternational Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 1998
الدولة/الإقليمالدنمارك
المدينةAalborg
المدة١٨/٠٧/٩٨١٩/٠٧/٩٨

ملاحظة ببليوغرافية

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1998.

بصمة

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

قم بذكر هذا