
For FullText 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 NodeWeighted 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.E96D
No.2
pp.270277 Publication Date: 2013/02/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E96.D.270
Print ISSN: 09168532 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 vertexdisjoint 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 polynomialtime algorithm, including a preprocessing method and another bottomup scheme with dynamic programming. With experimental studies, we show that our algorithm outperforms another prior algorithm presented by Ito et al. greatly.

