A note on Rooted Survivable Networks

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


The (undirected) Rooted Survivable Network Design (Rooted SND) problem is: given a complete graph on node set V with edge-costs, a root s ∈ V, and (node-)connectivity requirements {r (t) : t ∈ T ⊆ V}, find a minimum cost subgraph G that contains r (t) internally-disjoint st-paths for all t ∈ T. For large values of k = maxt ∈ T r (t) Rooted SND is at least as hard to approximate as Directed Steiner Tree [Y. Lando, Z. Nutov, Inapproximability of survivable networks, Theoret. Comput. Sci. 410 (21-23) (2009) 2122-2125]. For Rooted SND, [J. Chuzhoy, S. Khanna, Algorithms for single-source vertex-connectivity, in: FOCS, 2008, pp. 105-114] gave recently an approximation algorithm with ratio O (k2 log n). Independently, and using different techniques, we obtained at the same time a simpler primal-dual algorithm with the same ratio.

שפה מקוריתאנגלית
עמודים (מ-עד)1114-1119
מספר עמודים6
כתב עתInformation Processing Letters
מספר גיליון19
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 15 ספט׳ 2009

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A note on Rooted Survivable Networks'. יחד הם יוצרים טביעת אצבע ייחודית.

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