Tight approximation algorithm for connectivity augmentation problems

Guy Kortsarz, Zeev Nutov

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


The S-connectivity λGS(u, v) of (u, v) in a graph G is the maximum number of uv-paths that no two of them have an odgo or a node in S - {u, v} in common. The corresponding Connectivity Augmentation (CA) problem is: given a graph Go = (V, E0), S ⊆ V, and requirements r(u,v) on V × V, find a minimum size set F of new edges (any edge is allowed) so that λG0+FS(u, v) ≥ r(u, v) for all u, v ε V. Extensively studied particular cases are the edge-CA (when S = Ø) and the node-CA (when S = V). A. Frank gave a polynomial algorithm for undirected edge-CA and observed that the directed case even with r(u, v) ε {0,1} is at least as hard as the Set-Cover problem. Both directed and undirected node-CA have approximation threshold Ω(2log1-E n). We give an approximation algorithm that matches these approximation thresholds. For both directed and undirected CA with arbitrary requirements our approximation ratio is: O(log n) for S ≠ V arbitrary, and O(rmax · log n) for S = V, where rmax = maxu,vεV r(u, v).

שפה מקוריתאנגלית
כותר פרסום המארחAutomata, Languages and Programming - 33rd International Colloquium, ICALP 2006, Proceedings
מוציא לאורSpringer Verlag
מספר עמודים10
מסת"ב (מודפס)3540359044, 9783540359043
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2006
אירוע33rd International Colloquium on Automata, Languages and Programming, ICALP 2006 - Venice, איטליה
משך הזמן: 10 יולי 200614 יולי 2006

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך4051 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349


כנס33rd International Colloquium on Automata, Languages and Programming, ICALP 2006

טביעת אצבע

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

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