TY - JOUR
T1 - A tight bound on the min-ratio edge-partitioning problem of a tree
AU - Chu, An Chiang
AU - Wu, Bang Ye
AU - Wang, Hung Lung
AU - Chao, Kun Mao
N1 - Funding Information:
The authors would like to thank Hsiao-Fei Liu and the anonymous reviewers for improving the presentation of the paper. An-Chiang Chu, Hung-Lung Wang and Kun-Mao Chao were supported in part by NSC grants 95-2221-E-002-078 , 95-2221-E-002-126-MY3 , and 96-2221-E-002-034 from the National Science Council, Taiwan . Bang Ye Wu was supported in part by NSC grants 94-2213-E-366-006 and 95-2221-E-366-003 from the National Science Council, Taiwan .
PY - 2010/7/28
Y1 - 2010/7/28
N2 - In this paper, we study how to partition a tree into edge-disjoint subtrees of approximately the same size. Given a tree T with n edges and a positive integer k ≤ n, we design an algorithm to partition T into k edge-disjoint subtrees such that the ratio of the maximum number to the minimum number of edges of the subtrees is at most two. The best previous upper bound of the ratio is three, given by Wu et al. [B.Y. Wu, H.-L. Wang, S.-T. Kuan, K.-M. Chao, On the uniform edge-partition of a tree, Discrete Applied Mathematics 155 (10) (2007) 1213-1223]. Wu et al. also showed that for some instances, it is impossible to achieve a ratio better than two. Therefore, there is a lower bound of two on the ratio. It follows that the ratio upper bound attained in this paper is already tight.
AB - In this paper, we study how to partition a tree into edge-disjoint subtrees of approximately the same size. Given a tree T with n edges and a positive integer k ≤ n, we design an algorithm to partition T into k edge-disjoint subtrees such that the ratio of the maximum number to the minimum number of edges of the subtrees is at most two. The best previous upper bound of the ratio is three, given by Wu et al. [B.Y. Wu, H.-L. Wang, S.-T. Kuan, K.-M. Chao, On the uniform edge-partition of a tree, Discrete Applied Mathematics 155 (10) (2007) 1213-1223]. Wu et al. also showed that for some instances, it is impossible to achieve a ratio better than two. Therefore, there is a lower bound of two on the ratio. It follows that the ratio upper bound attained in this paper is already tight.
KW - Algorithm
KW - Optimization problem
KW - Partition
KW - Tree
UR - https://www.scopus.com/pages/publications/77953959070
UR - https://www.scopus.com/pages/publications/77953959070#tab=citedBy
U2 - 10.1016/j.dam.2010.05.014
DO - 10.1016/j.dam.2010.05.014
M3 - Article
AN - SCOPUS:77953959070
SN - 0166-218X
VL - 158
SP - 1471
EP - 1478
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 14
ER -