کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419210 | 683753 | 2016 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Algorithms to approximately count and sample conforming colorings of graphs
ترجمه فارسی عنوان
الگوریتم هایی برای تعداد تقریبی و رنگهای نمونه منطبق نمودار ها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگهای اقتباس؛ زنجیر مارکف؛ مجموعه مستقل؛ رنگهای HH
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a multigraph GG and a function FF that assigns a forbidden ordered pair of colors to each edge ee, we say a coloring CC of the vertices is conforming to FF if for all e=(u,v)e=(u,v), (C(u),C(v))≠F(e)(C(u),C(v))≠F(e). Conforming colorings generalize many natural graph theoretic concepts, including independent sets, vertex colorings, list colorings, HH-colorings and adapted colorings and consequently there are known complexity barriers to sampling and counting. We introduce natural Markov chains on the set of conforming colorings and provide general conditions for when they can be used to design efficient Monte Carlo algorithms for sampling and approximate counting.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 133–149
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 133–149
نویسندگان
Sarah Miracle, Dana Randall,