國立臺灣大學資訊工程學系Wu, Bang-YeBang-YeWuWang, Hung-LungHung-LungWangKuan, Shih-TaShih-TaKuanChao, Kun-MaoKun-MaoChao2006-09-272018-07-052006-09-272018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/20060927122859992217We 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. (Proofs for k = 3 and k = 4 are omitted here.) 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.application/pdf145571 bytesapplication/pdfzh-TWtreepartitionoptimization problemalgorithmotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/20060927122859992217/1/a_note_tree_splitting.pdf