کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426837 | 686310 | 2010 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
About randomised distributed graph colouring and graph partition algorithms
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We present and analyse a very simple randomised distributed vertex colouring algorithm for arbitrary graphs of size n that halts in time O(logn) with probability 1-o(n-1). Each message containing 1 bit, its bit complexity per channel is O(logn).From this algorithm, we deduce and analyse a randomised distributed vertex colouring algorithm for arbitrary graphs of maximum degree Δ and size n that uses at most Δ+1 colours and halts in time O(logn) with probability 1-o(n-1).We also obtain a partition algorithm for arbitrary graphs of size n that builds a spanning forest in time O(logn) with probability 1-o(n-1). We study some parameters such as the number, the size and the radius of trees of the spanning forest.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 208, Issue 11, November 2010, Pages 1296-1304
Journal: Information and Computation - Volume 208, Issue 11, November 2010, Pages 1296-1304