A tight bound on the min-ratio edge-partitioning problem of a tree

An Chiang Chu, Bang Ye Wu, Hung Lung Wang, Kun Mao Chao*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

In this paper, we study how to partition a tree into edge-disjoint subtrees of approximately the same size. Given a tree T with n edges and a positive integer k ≤ n, we design an algorithm to partition T into k edge-disjoint subtrees such that the ratio of the maximum number to the minimum number of edges of the subtrees is at most two. The best previous upper bound of the ratio is three, given by Wu et al. [B.Y. Wu, H.-L. Wang, S.-T. Kuan, K.-M. Chao, On the uniform edge-partition of a tree, Discrete Applied Mathematics 155 (10) (2007) 1213-1223]. Wu et al. also showed that for some instances, it is impossible to achieve a ratio better than two. Therefore, there is a lower bound of two on the ratio. It follows that the ratio upper bound attained in this paper is already tight.

Original languageEnglish
Pages (from-to)1471-1478
Number of pages8
JournalDiscrete Applied Mathematics
Volume158
Issue number14
DOIs
Publication statusPublished - 2010 Jul 28
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 'A tight bound on the min-ratio edge-partitioning problem of a tree'. Together they form a unique fingerprint.

Cite this