کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949966 | 1440208 | 2016 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Counting 4Ã4 matrix partitions of graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a symmetric matrix Mâ{0,1,â}DÃD, an M-partition of a graph G is a function from V(G) to D such that no edge of G is mapped to a 0 of M and no non-edge to a 1. We give a computer-assisted proof that, when |D|=4, the problem of counting the M-partitions of an input graph is either in FP or is #P-complete. Tractability is proved by reduction to the related problem of counting list M-partitions; intractability is shown using a gadget construction and interpolation. We use a computer program to determine which of the two cases holds for all but a small number of matrices, which we resolve manually to establish the dichotomy. We conjecture that the dichotomy also holds for |D|>4. More specifically, we conjecture that, for any symmetric matrix Mâ{0,1,â}DÃD, the complexity of counting M-partitions is the same as the related problem of counting list M-partitions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 213, 20 November 2016, Pages 76-92
Journal: Discrete Applied Mathematics - Volume 213, 20 November 2016, Pages 76-92
نویسندگان
Martin Dyer, Leslie Ann Goldberg, David Richerby,