کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430776 | 688145 | 2008 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient algorithms for counting parameterized list H-colorings
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the fixed parameter tractability of the counting version of a parameterization of the restrictive list H-coloring problem. The parameterization is defined by fixing the number of preimages of a subset C of the vertices in H through a weight assignment K on C. We show the fixed parameter tractability of counting the number of list (H,C,K)-colorings, for the case in which (H,C,K) is simple. We introduce the concept of compactor and a new algorithmic technique, compactor enumeration, that allow us to design fixed parameter algorithms for parameterized counting problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 74, Issue 5, August 2008, Pages 919-937
Journal: Journal of Computer and System Sciences - Volume 74, Issue 5, August 2008, Pages 919-937