For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/02/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
tree partition, operator scheduling, dynamic programming, distributed computing,
Full Text: PDF(591.8KB)>>
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.