Decomposing trees with large diameter

作者：Ravaux Romain^*

来源：Theoretical Computer Science, 2010, 411(34-36): 3068-3072.

DOI：10.1016/j.tcs.2010.04.032

• Arbitrarily partitionable trees
• Integer partition
• Diameter

An n-vertex graph is said to be decomposable for a partition (lambda(1), ...., lambda(p)) of the integer n if there exists a sequence (V(1), ...., V(p)) of connected vertex-disjoint subgraphs with vertical bar V(i)vertical bar = lambda(i). An n-vertex graph is said to be decomposable if this graph is decomposable for all the partitions of the integer n. We are interested in decomposable trees with large diameter. We show that any n-vertex tree T with diameter n - alpha is decomposable for all the partitions of n which contain at least alpha distinct integers. This structural result provides an algorithm to decide if an n-vertex tree T with diameter n - alpha, is decomposable in time n(0(alpha)).

• 出版日期2010-7-17