An Efficient Algorithm for Node-Weighted Tree Partitioning with Subtrees' Weights in a Given Range

作者：Luo, Guangchun^*; Chen, Hao; Qu, Caihui; Liu, Yuhai; Qin, Ke

来源：IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2013, E96D(2): 270-277.

DOI：10.1587/transinf.E96.D.270

• tree partition
• operator scheduling
• dynamic programming
• distributed computing

Tree partitioning arises in many parallel and distributed computing applications and storage systems. Some operator scheduling problems need to partition a tree into a number of vertex-disjoint subtrees such that some constraints are satisfied and some criteria are optimized. Given a tree T with each vertex or node assigned a nonnegative integer weight, two nonnegative integers l and u (l < u), and a positive integer p, we consider the following tree partitioning problems: partitioning T into minimum number of subtrees or p subtrees, with the condition that the sum of node weights in each subtree is at most u and at least l. To solve the two problems, we provide a fast polynomial-time algorithm, including a preprocessing method and another bottom-up scheme with dynamic programming. With experimental studies, we show that our algorithm outperforms another prior algorithm presented by Ito et al. greatly.

• 出版日期2013-2
• 单位电子科技大学