On the uniform edge-partition of a tree

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)1213-1223
Number of pages11
JournalDiscrete Applied Mathematics
Volume155
Issue number10
DOIs
Publication statusPublished - 2007 May 15
Externally publishedYes

Keywords

  • Algorithm
  • Optimization problem
  • Partition
  • Tree

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On the uniform edge-partition of a tree'. Together they form a unique fingerprint.

Cite this