کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419117 | 681743 | 2007 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the uniform edge-partition of a tree
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the uniform edge-partition of a tree On the uniform edge-partition of a tree](/preview/png/419117.png)
چکیده انگلیسی
We study the problem of uniformly partitioning the edge set of a tree with n edges into k connected components, where k⩽nk⩽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⩽4k⩽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(nlogk)O(nlogk) time. Experimental results on random trees are also shown.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 10, 15 May 2007, Pages 1213–1223
Journal: Discrete Applied Mathematics - Volume 155, Issue 10, 15 May 2007, Pages 1213–1223
نویسندگان
Bang Ye Wu, Hung-Lung Wang, Shih Ta Kuan, Kun-Mao Chao,