کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437685 690174 2015 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
چکیده انگلیسی

A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or injective, respectively. We prove that the problems of testing whether a given graph G allows a homomorphism to a given graph H that is locally bijective, surjective, or injective, respectively, are NP-complete, even when G has pathwidth at most 5, 4, or 2, respectively, or when both G and H have maximum degree 3. We complement these hardness results by showing that the three problems are polynomial-time solvable if G has bounded treewidth and in addition G or H has bounded maximum degree.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 590, 26 July 2015, Pages 86–95
نویسندگان
, , , , ,