کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657701 | 690091 | 2005 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Additive sparse spanners for graphs with bounded length of largest induced cycle
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we show that every chordal graph with n vertices and m edges admits an additive 4-spanner with at most 2n-2 edges and an additive 3-spanner with at most O(nlogn) edges. This significantly improves results of Peleg and Schäffer from [Graph Spanners, J. Graph Theory 13 (1989) 99-116]. Our spanners are additive and easier to construct. An additive 4-spanner can be constructed in linear time while an additive 3-spanner is constructable in O(mlogn) time. Furthermore, our method can be extended to graphs with largest induced cycles of length k. Any such graph admits an additive (k+1)-spanner with at most 2n-2 edges which is constructable in O(nk+m) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 347, Issues 1â2, 30 November 2005, Pages 54-75
Journal: Theoretical Computer Science - Volume 347, Issues 1â2, 30 November 2005, Pages 54-75
نویسندگان
Victor D. Chepoi, Feodor F. Dragan, Chenyu Yan,