کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419127 681743 2007 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A subexponential algorithm for the coloured tree partition problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A subexponential algorithm for the coloured tree partition problem
چکیده انگلیسی

Given a tree of nn vertices and a list of feasible colours for each vertex, the coloured tree partition problem (CTPP  ) consists in partitioning the tree into pp vertex-disjoint subtrees of minimum total cost, and assigning to each subtree a different colour, which must be feasible for all of its vertices. The problem is strongly NPNP-hard on general graphs, as well as on grid and bipartite graphs. This paper deals with the previously open case of tree graphs, showing that it is strongly NPNP-complete to determine whether a feasible solution exists. It presents reduction, decomposition and bounding procedures to simplify the problem and an exact algorithm of O(nplog2(ap-2)) complexity (with a>32) for the special case in which a vertex of each subtree is given.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 10, 15 May 2007, Pages 1326–1335
نویسندگان
,