کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334287 | 690361 | 2005 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
H-Coloring dichotomy revisited
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The H-Coloring problem can be expressed as a particular case of the constraint satisfaction problem (CSP) whose computational complexity has been intensively studied under various approaches in the last several years. We show that the dichotomy theorem proved by Hell and NeÅ¡etÅil [On the complexity of H-coloring, J. Combin. Theory Ser. B 48 (1990) 92-110] for the complexity of the H-Coloring problem for undirected graphs can be obtained using general methods for studying CSP, and that the criterion distinguishing the tractable cases of the H-Coloring problem agrees with that conjectured in [A.A. Bulatov, P.G. Jeavons, A.A. Krokhin, Constraint satisfaction problems and finite algebras, in: Proc. 27th Internat. Colloq. on Automata, Languages and Programming-ICALP'00, Lecture Notes in Computer Science, Vol. 1853, Springer, Berlin, 2000, pp. 272-282] for the complexity of the general CSP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 349, Issue 1, 12 December 2005, Pages 31-39
Journal: Theoretical Computer Science - Volume 349, Issue 1, 12 December 2005, Pages 31-39
نویسندگان
Andrei A. Bulatov,