کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433835 | 689635 | 2015 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity dichotomy for oriented homomorphism of planar graphs with large girth
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider the complexity of oriented homomorphism and two of its variants, namely strong oriented homomorphism and pushable homomorphism, for planar graphs with large girth. In each case, we consider the smallest target graph such that the corresponding homomorphism is NP-complete. These target graphs T4T4, T5T5, and T6T6 have 4, 5, and 6 vertices, respectively. For i∈{4,5,6}i∈{4,5,6} and for every g, we prove that if there exists a (bipartite) planar oriented graph with girth at least g that does not map to TiTi, then deciding homomorphism to TiTi is NP-complete for (bipartite) planar oriented graphs with girth at least g.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 596, 6 September 2015, Pages 142–148
Journal: Theoretical Computer Science - Volume 596, 6 September 2015, Pages 142–148
نویسندگان
Guillaume Guégan, Pascal Ochem,