Approximating k-outconnected subgraph problems

Joseph Cheriyan; Tibor Jordàn; Zeev Nutov

doi:10.1007/BFb0053965

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
المعرِّفات الرقمية للأشياء	https://doi.org/10.1007/BFb0053965
حالة النشر	نُشِر - 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.

الوصول إلى المستند

10.1007/BFb0053965

الملفات والروابط الأخرى

Link to publication in Scopus

قم بذكر هذا

Cheriyan, J., Jordàn, T., & Nutov, Z. (1998). Approximating k-outconnected subgraph problems. في J. Rolim, & K. Jansen (المحررون), Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings (الصفحات 77-88). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); المجلد 1444). Springer Verlag. https://doi.org/10.1007/BFb0053965

Cheriyan, Joseph ; Jordàn, Tibor ; Nutov, Zeev. / Approximating k-outconnected subgraph problems. Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings. محرر / José Rolim ; Klaus Jansen. Springer Verlag, 1998. الصفحات 77-88 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4d2dd37e452847ba85b061947d226912,

title = "Approximating k-outconnected subgraph problems",

abstract = "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{\textquoteright}s critical cycle theorem and (ii) an extension of a splitting off theorem by Bienstock et al.",

author = "Joseph Cheriyan and Tibor Jord{\`a}n and Zeev Nutov",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1998.; International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 1998 ; Conference date: 18-07-1998 Through 19-07-1998",

year = "1998",

doi = "10.1007/BFb0053965",

language = "אנגלית",

isbn = "3540647368",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "77--88",

editor = "Jos{\'e} Rolim and Klaus Jansen",

booktitle = "Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings",

address = "גרמניה",

}

Cheriyan, J, Jordàn, T & Nutov, Z 1998, Approximating k-outconnected subgraph problems. في J Rolim & K Jansen (المحررون), Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), المجلد 1444, Springer Verlag, الصفحات 77-88, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 1998, Aalborg, الدنمارك, ١٨/٠٧/٩٨. https://doi.org/10.1007/BFb0053965

Approximating k-outconnected subgraph problems. / Cheriyan, Joseph; Jordàn, Tibor; Nutov, Zeev.
Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings. محرر / José Rolim; Klaus Jansen. Springer Verlag, 1998. صفحة 77-88 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); المجلد 1444).

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

TY - GEN

T1 - Approximating k-outconnected subgraph problems

AU - Cheriyan, Joseph

AU - Jordàn, Tibor

AU - Nutov, Zeev

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1998.

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0002395698

U2 - 10.1007/BFb0053965

DO - 10.1007/BFb0053965

M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???

AN - SCOPUS:0002395698

SN - 3540647368

SN - 9783540647362

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 77

EP - 88

BT - Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings

A2 - Rolim, José

A2 - Jansen, Klaus

PB - Springer Verlag

T2 - International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 1998

Y2 - 18 July 1998 through 19 July 1998

ER -

Cheriyan J, Jordàn T, Nutov Z. Approximating k-outconnected subgraph problems. في Rolim J, Jansen K, المحررون, Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings. Springer Verlag. 1998. صفحة 77-88. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0053965

Approximating k-outconnected subgraph problems

ملخص

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

!!Conference

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

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا