Wu, Bang YeBang YeWuWang, Hung-LungHung-LungWangTa Kuan, ShihShihTa KuanKUN-MAO CHAO2009-04-292018-07-052009-04-292018-07-0520070166218Xhttp://ntur.lib.ntu.edu.tw//handle/246246/154549https://www.scopus.com/inward/record.uri?eid=2-s2.0-34247142379&doi=10.1016%2fj.dam.2006.10.012&partnerID=40&md5=ef7247b1214c107531c9ae272b4456f1We 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. © 2006 Elsevier B.V. All rights reserved.application/pdf201283 bytesapplication/pdfen-USAlgorithm; Optimization problem; Partition; Treejournal article10.1016/j.dam.2006.10.0122-s2.0-34247142379http://ntur.lib.ntu.edu.tw/bitstream/246246/154549/1/14.pdf