Publication: On the uniform edge-partition of a tree
Loading...
Date
2007
Authors
Wu, Bang Ye
Wu, Bang Ye; Wang, Hung-Lung; Kuan, Shih Ta; Chao, Kun-Mao
Wang, Hung-Lung
Ta Kuan, Shih
KUN-MAO CHAO
Journal Title
Journal ISSN
Volume Title
Publisher
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 (n log k) time. Experimental results on random trees are also shown. © 2006 Elsevier B.V. All rights reserved.
Description
Keywords
Algorithm; Optimization problem; Partition; Tree