A note on Rooted Survivable Networks

作者：Nutov Zeev^*

来源：Information Processing Letters, 2009, 109(19): 1114-1119.

DOI：10.1016/j.ipl.2009.07.011

• Rooted node-connectivity
• Network design
• Approximation algorithms

The (undirected) Rooted Survivable Network Design (Rooted SND) problem is: given a complete graph on node set V with edge-costs, a root s epsilon V. and (node-)connectivity requirements {r(t): t epsilon T subset of V}, find a minimum cost subgraph G that contains r(t) internally-disjoint st-paths for all t epsilon T. For large values of k = max(t epsilon 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(k(2)logn). Independently, and using different techniques, we obtained at the same time a simpler primal-dual algorithm with the same ratio.

• 出版日期2009-9-15