کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903496 | 1632569 | 2017 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Strong intractability of generalized convex recoloring problems
ترجمه فارسی عنوان
ناکارآیی شدید مشکلات مجدد محدب تعمیم یافته
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مجدد محدب سختی غیر قابل تصور بودن پارامتر نشده
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A coloring of the vertices of a connected graph is r-convex if each color class induces a subgraph with at most r components. We address the r-convex recoloring problem defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G so that the resulting coloring is r-convex. This problem, known to be NP-hard even on paths, was first investigated on trees and for r=1, motivated by applications on perfect phylogenies. The concept of r-convexity, for râ¥2, was proposed later, and it is also of interest in the study of protein-protein interaction networks and phylogenetic networks. Here, we show that, for each râN, the r-convex recoloring problem on n-vertex bipartite graphs cannot be approximated within a factor of n1âε for any ε>0, unless P=NP. We also provide strong hardness results for weighted and parametrized versions of the problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 93-98
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 93-98
نویسندگان
Phablo F.S. Moura, Yoshiko Wakabayashi,