کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872424 | 681651 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Recognizing vertex intersection graphs of paths on bounded degree trees
ترجمه فارسی عنوان
تشخیص نمودارهای تقاطع ریشه مسیرها در درختان درجه محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An undirected graph G is called a VPT graph if it is the vertex intersection graph of a family of paths in a tree. Thus, [h,2,1] graphs are the VPT graphs that can be represented in a tree with maximum degree at most h. In this paper we characterize [h,2,1] graphs using chromatic number. We show that the problem of deciding whether a given VPT graph belongs to [h,2,1] is NP-complete, while the problem of deciding whether the graph belongs to [h,2,1]â[hâ1,2,1] is NP-hard. Both problems remain hard even when restricted to VPTâ©Split. Additionally, we present a non-trivial subclass of VPTâ©Split in which these problems are polynomial time solvable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 70-77
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 70-77
نویسندگان
L. Alcón, M. Gutierrez, M.P. Mazzoleni,