Name
Title | ||
|---|---|---|
An Efficient Algorithm For Node-Weighted Tree Partitioning With Subtrees' Weights In A Given Range |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1587/transinf.E96.D.270 | IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS |
Keywords | Field | DocType |
tree partition, operator scheduling, dynamic programming, distributed computing | Combinatorics,Tree rotation,Computer science,Vantage-point tree,T-tree,K-ary tree,Tree (data structure),Algorithm,Fractal tree index,Interval tree,Search tree | Journal |
Volume | Issue | ISSN |
E96D | 2 | 1745-1361 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
5 | ||