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

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