תקציר
A graph G is k-connected if it has k internally-disjoint stpaths for every pair s, t of nodes. Given a root s and a set T of terminals is k-(s, T)-connected if it has k internally-disjoint st-paths for every t ε T. We consider two well studied mincost connectivity augmentation problems, where we are given an integer k ≥ 0, a graph G = (V,E), and and an edge set F on V with costs. The goal is to compute a minimum cost edge set J ⊆ F such that G + J has connectivity k + 1. In the k-Connectivity Augmentation problem G is k-connected and G+J should be (k+1)-connected. In the k-(s, T)-Connectivity Augmentation problem G is k-(s, T)-connected and G + J should be (k + 1)-(s, T)-connected. For the k-Connectivity Augmentation problem we obtain the following results. For n ≥ 3k - 5, we obtain approximation ratios 3 for directed graphs and 4 for undirected graphs,improving the previous ratio 5 of [26]. For directed graphs and k = 1, or k = 2 and n odd, we further improve to 2.5 the previous ratios 3 and 4, respectively. For the undirected 2-(s, T)-Connectivity Augmentation problem we achieve ratio 4 2/3, improving the previous best ratio 12 of [24]. For the special case when all the edges in F are incident to s, we give a polynomial time algorithm, improving the ratio 4 17/30 of [21,25] for this variant.
שפה מקורית | אנגלית |
---|---|
כותר פרסום המארח | Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia, CSR 2016, Proceedings |
עורכים | Gerhard J. Woeginger, Alexander S. Kulikov |
מוציא לאור | Springer Verlag |
עמודים | 324-339 |
מספר עמודים | 16 |
מסת"ב (מודפס) | 9783319341705 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - 2016 |
אירוע | 11th International Computer Science Symposium in Russia, CSR 2016 - St. Petersburg, רוסיה משך הזמן: 9 יוני 2016 → 13 יוני 2016 |
סדרות פרסומים
שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
כרך | 9691 |
ISSN (מודפס) | 0302-9743 |
ISSN (אלקטרוני) | 1611-3349 |
כנס
כנס | 11th International Computer Science Symposium in Russia, CSR 2016 |
---|---|
מדינה/אזור | רוסיה |
עיר | St. Petersburg |
תקופה | 9/06/16 → 13/06/16 |
הערה ביבליוגרפית
Publisher Copyright:© Springer International Publishing Switzerland 2016.