Given a tree of $n$ vertices and a list of feasible colours for each vertex, the \emph{Coloured Tree Partition Problem\/} (\emph{CTPP\/}) consists in partitioning the tree into $p$ 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 $\mathcal{NP}$-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 $\mathcal{NP}$-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( n \, p^{\log_{2}\left( a\sqrt{p-2} \right)} )$ complexity (with $a > 3\sqrt{2}$) for the special case in which a vertex of each subtree is given.
A subexponential algorithm for the coloured tree partition problem / R. Cordone. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 155:10(2007 May), pp. 1326-1335.
A subexponential algorithm for the coloured tree partition problem
R. CordonePrimo
2007
Abstract
Given a tree of $n$ vertices and a list of feasible colours for each vertex, the \emph{Coloured Tree Partition Problem\/} (\emph{CTPP\/}) consists in partitioning the tree into $p$ 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 $\mathcal{NP}$-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 $\mathcal{NP}$-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( n \, p^{\log_{2}\left( a\sqrt{p-2} \right)} )$ complexity (with $a > 3\sqrt{2}$) for the special case in which a vertex of each subtree is given.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.