Improved approximation algorithms for min-cost connectivity augmentation problems

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

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 יוני 201613 יוני 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/1613/06/16

הערה ביבליוגרפית

Publisher Copyright:
© Springer International Publishing Switzerland 2016.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Improved approximation algorithms for min-cost connectivity augmentation problems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי