Edge separators for quasi-binary trees

DOI10.1016/J.DAM.2014.12.004zbMATH Open1338.05044arXiv1209.3572OpenAlexW2053774048MaRDI QIDQ299105FDOQ299105

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

Publication date: 22 June 2016

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

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.

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

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

zbMATH Keywords

binary treeseparators

Mathematics Subject Classification ID

Trees (05C05)

Cites Work

• A Separator Theorem for Planar Graphs
• \(N\)-separators in planar graphs
• Edge separators for graphs of bounded genus with applications
• Title not available (Why is that?)

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)