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 · 2013
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