On the uniform edge-partition of a tree

Bang Ye Wu*, Hung Lung Wang, Shih T. Ta Kuan, Kun Mao Chao

*此作品的通信作者

研究成果: 雜誌貢獻期刊論文同行評審

7 引文 斯高帕斯(Scopus)

摘要

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.

原文英語
頁(從 - 到)1213-1223
頁數11
期刊Discrete Applied Mathematics
155
發行號10
DOIs
出版狀態已發佈 - 2007 五月 15
對外發佈

ASJC Scopus subject areas

  • 離散數學和組合
  • 應用數學

指紋

深入研究「On the uniform edge-partition of a tree」主題。共同形成了獨特的指紋。

引用此