תקציר
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 |
| מזהי עצם דיגיטלי (DOIs) | |
| סטטוס פרסום | פורסם - 1998 |
| פורסם באופן חיצוני | כן |
| אירוע | International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 1998 - Aalborg, דנמרק משך הזמן: 18 יולי 1998 → 19 יולי 1998 |
סדרות פרסומים
| שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| כרך | 1444 |
| ISSN (מודפס) | 0302-9743 |
| ISSN (אלקטרוני) | 1611-3349 |
כנס
| כנס | International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 1998 |
|---|---|
| מדינה/אזור | דנמרק |
| עיר | Aalborg |
| תקופה | 18/07/98 → 19/07/98 |
הערה ביבליוגרפית
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 1998.