کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435911 | 689950 | 2015 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fault tolerant additive and (μ,α)(μ,α)-spanners
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Graph spanners are sparse subgraphs that preserve the distances of the original graph up to some approximation ratio (the spanner's stretch). A number of algorithms are known for constructing sparse spanners with small multiplicative or additive stretch. Recently, algorithms were introduced for constructing fault-tolerant multiplicative spanners of general graphs. This paper addresses the analogous problem of constructing fault tolerant additive and (μ,α)(μ,α)-spanners for general graphs, and presents a number of (deterministic and randomized) construction algorithms for such spanners.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 580, 17 May 2015, Pages 94–100
Journal: Theoretical Computer Science - Volume 580, 17 May 2015, Pages 94–100
نویسندگان
Gilad Braunschvig, Shiri Chechik, David Peleg, Adam Sealfon,