کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333007 | 688167 | 2005 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we first show how to compute connected and weakly connected dominating sets whose size is at most O(logÎ) times the optimum, Î being the maximum degree of the input network. This is best-possible if NPâDTIME[nO(loglogn)] and if the processors are required to run in polynomial-time. We then show how to construct dominating sets that have the above properties, as well as the “low stretch” property that any two adjacent nodes in the network have their dominators at a distance of at most O(logn) in the output network. (Given a dominating set S, a dominator of a vertex u is any vâS such that the distance between u and v is at most one.) We also show our time bounds to be essentially optimal.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 71, Issue 4, November 2005, Pages 467-479
Journal: Journal of Computer and System Sciences - Volume 71, Issue 4, November 2005, Pages 467-479
نویسندگان
Devdatt Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, Aravind Srinivasan,