Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.dam.2010.05.014 | Discrete Applied Mathematics |
Keywords | Field | DocType |
k edge-disjoint,algorithm,minimum number,optimization problem,positive integer k,partition,edge-disjoint subtrees,tree,min-ratio edge-partitioning problem,uniform edge-partition,maximum number,discrete applied mathematics,n edge,upper bound,lower bound | Integer,Discrete mathematics,Combinatorics,Upper and lower bounds,Partition (number theory),Optimization problem,Mathematics | Journal |
Volume | Issue | ISSN |
158 | 14 | Discrete Applied Mathematics |
Citations | PageRank | References |
1 | 0.36 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| An-Chiang Chu | 1 | 7 | 2.18 |
| Bang Ye Wu | 2 | 336 | 33.89 |
| Hung-Lung Wang | 3 | 27 | 5.63 |
| Kun-mao Chao | 4 | 838 | 94.05 |