کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419225 | 683753 | 2016 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Edge separators for quasi-binary trees
ترجمه فارسی عنوان
جداساز لبه برای درختان شبه باینری
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
درخت باینری؛ جدا کننده
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
One wishes to remove k−1k−1 edges of a vertex-weighted tree TT such that the weights of the kk induced connected components are approximately the same. How well can one do it? In this paper, we investigate such kk-separators for quasi-binary trees. We show that, under certain conditions on the total weight of the tree, a particular kk-separator can be constructed such that the smallest (respectively the largest) weighted component is lower (respectively upper) bounded. Examples showing optimality for the lower bound are also given.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 284–289
Journal: Discrete Applied Mathematics - Volume 210, 10 September 2016, Pages 284–289
نویسندگان
Jorge Luis Ramírez Alfonsín, Serge Tishchenko,