| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419225 | Discrete Applied Mathematics | 2016 | 6 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jorge Luis Ramírez Alfonsín, Serge Tishchenko,