|
|||||
|
|
On the uniform edge-partition of a tree |
|
| Authors: | Bang Ye Wu Hung-Lung Wang |
| Institution: | a Department of Computer Science and Information Engineering, Shu-Te University, YenChau, KaoShiung 824, Taiwan, ROC b Department of Computer Science and Information Engineering, National Taiwan University, Taipei 106, Taiwan, ROC c Graduate Institute of Networking and Multimedia, National Taiwan University, Taipei 106, Taiwan, ROC |
| 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(nlogk) time. Experimental results on random trees are also shown. |
| Keywords: | Tree Partition Optimization problem Algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ | |