תקציר
The problem of finding a minimum weight k-vertex connected spanning subgraph is considered. For k>1, this problem is known to be NP-hard. Combining properties of inclusion-minimal k-vertex connected graphs and of k-out-connected graphs (i.e., graphs which contain a vertex from which there are k internally vertex-disjoint paths to every other vertex), we derive polynomial time approximation algorithms for several values of k. (i) For k=3, we give an algorithm with approximation factor 2. This improves the best previously known factor 3. (ii) For k= 4 and k= 5, we give an algorithm with approximation factor 3.
| שפה מקורית | אנגלית |
|---|---|
| כותר פרסום המארח | Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings |
| עורכים | Giancarlo Bongiovanni, Daniel Pierre Bovet, Giuseppe Di Battista |
| מוציא לאור | Springer Verlag |
| עמודים | 13-24 |
| מספר עמודים | 12 |
| מסת"ב (מודפס) | 3540625925, 9783540625926 |
| מזהי עצם דיגיטלי (DOIs) | |
| סטטוס פרסום | פורסם - 1997 |
| פורסם באופן חיצוני | כן |
| אירוע | 3rd Italian Conference on Algorithms and Complexity, CIAC 1997 - Rome, איטליה משך הזמן: 12 מרץ 1997 → 14 מרץ 1997 |
סדרות פרסומים
| שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| כרך | 1203 |
| ISSN (מודפס) | 0302-9743 |
| ISSN (אלקטרוני) | 1611-3349 |
כנס
| כנס | 3rd Italian Conference on Algorithms and Complexity, CIAC 1997 |
|---|---|
| מדינה/אזור | איטליה |
| עיר | Rome |
| תקופה | 12/03/97 → 14/03/97 |
הערה ביבליוגרפית
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 1997.