Edge separators for quasi-binary trees

DOI10.1016/J.DAM.2014.12.004MaRDI QIDQ299105zbMATH OpenOpenAlexFDO

Authors Serge Tishchenko, Jorge Luis Ramírez Alfonsín

Publication date 22 June 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.3572

zbMATH Keywords

binary treeseparators

Mathematics Subject Classification ID

Trees (05C05)

Abstract: One wishes to remove $k-1$ edges of a vertex-weighted tree $T$ such that the weights of the $k$ induced connected components are approximately the same. How well can one do it ? In this paper, we investigate such $k$-separator for {em quasi-binary} trees. We show that, under certain conditions on the total weight of the tree, a particular $k$-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.

Recommendations

• On the uniform edge-partition of a tree
• Partitioning a Weighted Tree to Subtrees of Almost Uniform Size
• scientific article; zbMATH DE number 3866593
• The \(k\)-separator problem
• A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees

Cites work

• scientific article; zbMATH DE number 16297 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• Edge separators for graphs of bounded genus with applications
• \(N\)-separators in planar graphs

Cited in

(1)

• Safe separators for treewidth

This page was built for publication: Edge separators for quasi-binary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q299105)