@article{35b3eb3efe244b33a65c4146a713ed36,

title = "On the uniform edge-partition of a tree",

abstract = "We study the problem of uniformly partitioning the edge set of a tree with n edges into k connected components, where k ≤ n. The objective is to minimize the ratio of the maximum to the minimum number of edges of the subgraphs in the partition. We show that, for any tree and k ≤ 4, there exists a k-split with ratio at most two. For general k, we propose a simple algorithm that finds a k-split with ratio at most three in O (n log k) time. Experimental results on random trees are also shown.",

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

author = "Wu, {Bang Ye} and Wang, {Hung Lung} and {Ta Kuan}, {Shih T.} and Chao, {Kun Mao}",

note = "Funding Information: We thank the referees for their helpful comments. Bang Ye Wu was supported in part by an NSC Grant 93-2213-E-366-014 from the National Science Council, Taiwan. Hung-Lung Wang and Kun-Mao Chao were supported in part by an NSC Grant 94-2213-E-002-091 from the National Science Council, Taiwan. ",

year = "2007",

month = may,

day = "15",

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

language = "English",

volume = "155",

pages = "1213--1223",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "10",

}