A note on the uniform edge-partition of a tree
Date Issued
2006
Date
2006
Author(s)
Wu, Bang-Ye
Wang, Hung-Lung
Kuan, Shih-Ta
Chao, Kun-Mao
DOI
20060927122859992217
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. (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.
Subjects
tree
partition
optimization problem
algorithm
Publisher
臺北市:國立臺灣大學資訊工程學系
Type
other
File(s)![Thumbnail Image]()
Loading...
Name
a_note_tree_splitting.pdf
Size
142.16 KB
Format
Adobe PDF
Checksum
(MD5):a7e0a19822f28e45ac9373d0eeaba72b