IEICE TRANSACTIONS on Information
An Efficient Algorithm for Node-Weighted Tree Partitioning with Subtrees' Weights in a Given Range
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E96-D No.2 pp.270-277
- Publication Date
- 2013/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E96.D.270
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Guangchun LUO, Hao CHEN, Caihui QU, Yuhai LIU, Ke QIN, "An Efficient Algorithm for Node-Weighted Tree Partitioning with Subtrees' Weights in a Given Range" in IEICE TRANSACTIONS on Information,
vol. E96-D, no. 2, pp. 270-277, February 2013, doi: 10.1587/transinf.E96.D.270.
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 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E96.D.270/_p
Copy
@ARTICLE{e96-d_2_270,
author={Guangchun LUO, Hao CHEN, Caihui QU, Yuhai LIU, Ke QIN, },
journal={IEICE TRANSACTIONS on Information},
title={An Efficient Algorithm for Node-Weighted Tree Partitioning with Subtrees' Weights in a Given Range},
year={2013},
volume={E96-D},
number={2},
pages={270-277},
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 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.},
keywords={},
doi={10.1587/transinf.E96.D.270},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - An Efficient Algorithm for Node-Weighted Tree Partitioning with Subtrees' Weights in a Given Range
T2 - IEICE TRANSACTIONS on Information
SP - 270
EP - 277
AU - Guangchun LUO
AU - Hao CHEN
AU - Caihui QU
AU - Yuhai LIU
AU - Ke QIN
PY - 2013
DO - 10.1587/transinf.E96.D.270
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E96-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2013
AB - 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.
ER -
English
