Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419127 | Discrete Applied Mathematics | 2007 | 10 Pages |
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.