کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333173 | 688607 | 2009 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Threshold dominating cliques in random graphs and interval routing
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The existence of (shortest-path) interval routing schemes for random graphs that use at most one interval label per edge is an open problem posed in [C. Gavoille, D. Peleg, The compactness of interval routing for almost all graphs, SIAM J. Computing 31 (3) (2001) 706-721]. In this paper, we show that for any random graph G(n,p) with edge probability p>0.765, there exists an interval routing scheme that uses at most one label per edge and has an additive stretch 1. In doing so, we provide an interesting construction of such an interval routing scheme for graphs that have a 12-threshold dominating clique, and establish a general result on the existence of threshold dominating cliques in random graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 519-532
Journal: Journal of Discrete Algorithms - Volume 7, Issue 4, December 2009, Pages 519-532
نویسندگان
Yong Gao,