کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433835 689635 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complexity dichotomy for oriented homomorphism of planar graphs with large girth
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Complexity dichotomy for oriented homomorphism of planar graphs with large girth
چکیده انگلیسی

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
نویسندگان
, ,