کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419225 683753 2016 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Edge separators for quasi-binary trees
ترجمه فارسی عنوان
جداساز لبه برای درختان شبه باینری
کلمات کلیدی
درخت باینری؛ جدا کننده
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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
نویسندگان
, ,