کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419127 | 681743 | 2007 | 10 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Applied Mathematics - Volume 155, Issue 10, 15 May 2007, Pages 1326–1335