A tight bound on the min-ratio edge-partitioning problem of a tree

An Chiang Chu; Bang Ye Wu; Hung Lung Wang; Kun Mao Chao

doi:10.1016/j.dam.2010.05.014

A tight bound on the min-ratio edge-partitioning problem of a tree

An Chiang Chu
, Bang Ye Wu
, Hung Lung Wang
, Kun Mao Chao^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

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.

Original language	English
Pages (from-to)	1471-1478
Number of pages	8
Journal	Discrete Applied Mathematics
Volume	158
Issue number	14
DOIs	https://doi.org/10.1016/j.dam.2010.05.014
Publication status	Published - 2010 Jul 28
Externally published	Yes

Keywords

Algorithm
Optimization problem
Partition
Tree

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2010.05.014

Cite this

@article{cec384550af94a24bf4ec122eb40a727,

title = "A tight bound on the min-ratio edge-partitioning problem of a tree",

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.",

keywords = "Algorithm, Optimization problem, Partition, Tree",

author = "Chu, \{An Chiang\} and Wu, \{Bang Ye\} and Wang, \{Hung Lung\} and Chao, \{Kun Mao\}",

note = "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 . ",

year = "2010",

month = jul,

day = "28",

doi = "10.1016/j.dam.2010.05.014",

language = "English",

volume = "158",

pages = "1471--1478",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier BV",

number = "14",

}

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 -

A tight bound on the min-ratio edge-partitioning problem of a tree

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this