کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438064 | 690225 | 2008 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Random sampling of colourings of sparse random graphs with a constant number of colours
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this work we present a simple and efficient algorithm which, with high probability, provides an almost uniform sample from the set of proper k-colourings on an instance of sparse random graphs Gn,d/n, where k=k(d) is a sufficiently large constant. Our algorithm is not based on the Markov Chain Monte Carlo method (M.C.M.C.). Instead, we provide a novel proof of correctness of our algorithm that is based on interesting “spatial mixing” properties of colourings of Gn,d/n. Our result improves upon previous results (based on M.C.M.C.) that required a number of colours growing unboundedly with n.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 407, Issues 1–3, 6 November 2008, Pages 134-154
Journal: Theoretical Computer Science - Volume 407, Issues 1–3, 6 November 2008, Pages 134-154