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

Guangchun LUO  Hao CHEN  Caihui QU  Yuhai LIU  Ke QIN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.2   pp.270-277
Publication Date: 2013/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E96.D.270
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
tree partition,  operator scheduling,  dynamic programming,  distributed computing,  

Full Text: PDF(591.8KB)
>>Buy this Article


Summary: 
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 pre-processing 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.