On the uniform edge-partition of a tree

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

doi:10.1016/j.dam.2006.10.012

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 journal › Article › peer-review

10 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 language	English
Pages (from-to)	1213-1223
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	155
Issue number	10
DOIs	https://doi.org/10.1016/j.dam.2006.10.012
Publication status	Published - 2007 May 15
Externally published	Yes

Keywords

Algorithm
Optimization problem
Partition
Tree

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2006.10.012

Cite this

@article{35b3eb3efe244b33a65c4146a713ed36,

title = "On the uniform edge-partition of a tree",

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.",

keywords = "Algorithm, Optimization problem, Partition, Tree",

author = "Wu, {Bang Ye} and Wang, {Hung Lung} and {Ta Kuan}, {Shih T.} and Chao, {Kun Mao}",

note = "Funding Information: We thank the referees for their helpful comments. Bang Ye Wu was supported in part by an NSC Grant 93-2213-E-366-014 from the National Science Council, Taiwan. Hung-Lung Wang and Kun-Mao Chao were supported in part by an NSC Grant 94-2213-E-002-091 from the National Science Council, Taiwan. ",

year = "2007",

month = may,

day = "15",

doi = "10.1016/j.dam.2006.10.012",

language = "English",

volume = "155",

pages = "1213--1223",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "10",

}

TY - JOUR

T1 - On the uniform edge-partition of a tree

AU - Wu, Bang Ye

AU - Wang, Hung Lung

AU - Ta Kuan, Shih T.

AU - Chao, Kun Mao

N1 - Funding Information: We thank the referees for their helpful comments. Bang Ye Wu was supported in part by an NSC Grant 93-2213-E-366-014 from the National Science Council, Taiwan. Hung-Lung Wang and Kun-Mao Chao were supported in part by an NSC Grant 94-2213-E-002-091 from the National Science Council, Taiwan.

PY - 2007/5/15

Y1 - 2007/5/15

N2 - 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.

AB - 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.

KW - Algorithm

KW - Optimization problem

KW - Partition

KW - Tree

UR - http://www.scopus.com/inward/record.url?scp=34247142379&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34247142379&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2006.10.012

DO - 10.1016/j.dam.2006.10.012

M3 - Article

AN - SCOPUS:34247142379

SN - 0166-218X

VL - 155

SP - 1213

EP - 1223

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 10

ER -

On the uniform edge-partition of a tree

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this