کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437792 690185 2009 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Inapproximability of survivable networks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Inapproximability of survivable networks
چکیده انگلیسی

In the Survivable Network Design Problem (SNDP) one seeks to find a minimum cost subgraph that satisfies prescribed node-connectivity requirements. We give a novel approximation ratio preserving reduction from Directed SNDP to Undirected SNDP. Our reduction extends and widely generalizes as well as significantly simplifies the main results of [G. Kortsarz, R. Krauthgamer, J.R. Lee, Hardness of approximation for vertex-connectivity network design problems, SIAM Journal on Computing 33 (3) (2004) 704–720]. Using it, we derive some new hardness of approximation results, as follows. We show that directed and undirected variants of SNDP and of k-Connected Subgraph are equivalent w.r.t. approximation, and that a ρ-approximation for Undirected Rooted SNDP implies a ρ-approximation for Directed Steiner Tree.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 21–23, 17 May 2009, Pages 2122-2125