کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949574 | 1440194 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The complexity of tropical graph homomorphisms
ترجمه فارسی عنوان
پیچیدگی هموگلوبین های گرافیکی استوایی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودارهای گرمسیری، هموروئید گراف دوقطبی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A tropical graph (H,c) consists of a graph H and a (not necessarily proper) vertex-colouring c of H. Given two tropical graphs (G,c1) and (H,c), a homomorphism of (G,c1) to (H,c) is a standard graph homomorphism of G to H that also preserves the vertex-colours. We initiate the study of the computational complexity of tropical graph homomorphism problems. We consider two settings. First, when the tropical graph (H,c) is fixed; this is a problem called (H,c)-Colouring. Second, when the colouring of H is part of the input; the associated decision problem is called H-Tropical-Colouring. Each (H,c)-Colouring problem is a constraint satisfaction problem (CSP), and we show that a complexity dichotomy for the class of (H,c)-Colouring problems holds if and only if the Feder-Vardi Dichotomy Conjecture for CSPs is true. This implies that (H,c)-Colouring problems form a rich class of decision problems. On the other hand, we were successful in classifying the complexity of at least certain classes of H-Tropical-Colouring problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 229, 1 October 2017, Pages 64-81
Journal: Discrete Applied Mathematics - Volume 229, 1 October 2017, Pages 64-81
نویسندگان
Florent Foucaud, Ararat Harutyunyan, Pavol Hell, Sylvain Legay, Yannis Manoussakis, Reza Naserasr,