کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420188 683902 2012 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The complexity of minimum convex coloring
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The complexity of minimum convex coloring
چکیده انگلیسی

A coloring of the vertices of a graph is called convex if each subgraph induced by all vertices of the same color is connected. We consider three variants of recoloring a colored graph with minimal cost such that the resulting coloring is convex. Two variants of the problem are shown to be NPNP-hard on trees even if in the initial coloring each color is used to color only a bounded number of vertices. For graphs of bounded treewidth, we present a polynomial-time (2+ϵ)(2+ϵ)-approximation algorithm for these two variants and a polynomial-time algorithm for the third variant. Our results also show that, unless NP⊆DTIME(nO(loglogn))NP⊆DTIME(nO(loglogn)), there is no polynomial-time approximation algorithm with a ratio of size (1−o(1))lnlnN(1−o(1))lnlnN for the following problem: given pairs of vertices in an undirected NN-vertex graph of bounded treewidth, determine the minimal possible number ll for which all except ll pairs can be connected by disjoint paths.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 6, April 2012, Pages 810–833
نویسندگان
, ,