کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950813 1441036 2017 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Randomly coloring simple hypergraphs with fewer colors
ترجمه فارسی عنوان
تصادفی رنگ آمیزی تصاویر ساده با رنگ های کمتر
کلمات کلیدی
تجزیه و تحلیل الگوریتم ها، زنجیره مارکوف مونت کارلو، رنگ آمیزی بیش از حد،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the problem of constructing a (near) uniform random proper q-coloring of a simple k-uniform hypergraph with n vertices and maximum degree Δ. (Proper in that no edge is mono-colored and simple in that two edges have maximum intersection of size one.) We show that if q≥max⁡{Cklog⁡n,500k3Δ1/(k−1)} then the Glauber Dynamics will become close to uniform in O(nlog⁡n) time, given a random (improper) start. This improves on the results in Frieze and Melsted [5].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 126, October 2017, Pages 39-42
نویسندگان
, ,