https://scholars.lib.ntu.edu.tw/handle/123456789/115176
標題: | A note on the uniform edge-partition of a tree | 作者: | Wu, Bang-Ye Wang, Hung-Lung Kuan, Shih-Ta Chao, Kun-Mao |
關鍵字: | tree;partition;optimization problem;algorithm | 公開日期: | 2006 | 出版社: | 臺北市:國立臺灣大學資訊工程學系 | 摘要: | 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. (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. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/20060927122859992217 | 其他識別: | 20060927122859992217 |
顯示於: | 資訊工程學系 |
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
a_note_tree_splitting.pdf | 142.16 kB | Adobe PDF | 檢視/開啟 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。