کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949732 | 1440204 | 2017 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of rainbow vertex connectivity problems for restricted graph classes
ترجمه فارسی عنوان
پیچیدگی مشکلات مربوط به اتصال به حلقهای رنگین کمان برای کلاسهای گراف محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
اتصال رنگین کمان، پیچیدگی محاسباتی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A path in a vertex-colored graph G is vertex rainbow if all of its internal vertices have a distinct color. The graph G is said to be rainbow vertex connected if there is a vertex rainbow path between every pair of its vertices. Similarly, the graph G is strongly rainbow vertex connected if there is a shortest path which is vertex rainbow between every pair of its vertices. We consider the complexity of deciding if a given vertex-colored graph is rainbow or strongly rainbow vertex connected. We call these problems Rainbow Vertex Connectivity and Strong Rainbow Vertex Connectivity, respectively. We prove both problems remain NP-complete on very restricted graph classes including bipartite planar graphs of maximum degree 3, interval graphs, and k-regular graphs for kâ¥3. We settle precisely the complexity of both problems from the viewpoint of two width parameters: pathwidth and tree-depth. More precisely, we show both problems remain NP-complete for bounded pathwidth graphs, while being fixed-parameter tractable parameterized by tree-depth. Moreover, we show both problems are solvable in polynomial time for block graphs, while Strong Rainbow Vertex Connectivity is tractable for cactus graphs and split graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 219, 11 March 2017, Pages 132-146
Journal: Discrete Applied Mathematics - Volume 219, 11 March 2017, Pages 132-146
نویسندگان
Juho Lauri,