کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419517 683829 2010 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A tight bound on the min-ratio edge-partitioning problem of a tree
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A tight bound on the min-ratio edge-partitioning problem of a tree
چکیده انگلیسی

In this paper, we study how to partition a tree into edge-disjoint subtrees of approximately the same size. Given a tree TT with nn edges and a positive integer k≤nk≤n, we design an algorithm to partition TT into kk 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 14, 28 July 2010, Pages 1471–1478
نویسندگان
, , , ,