A tight bound on the min-ratio edge-partitioning problem of a tree

DOI10.1016/J.DAM.2010.05.014MaRDI QIDQ608252zbMATH OpenOpenAlexFDO

Authors An-Chiang Chu, Bang Ye Wu, Hung-Lung Wang, Kun-Mao Chao

Publication date 25 November 2010

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

Full work available at URL https://doi.org/10.1016/j.dam.2010.05.014

zbMATH Keywords

treealgorithmpartitionoptimization problem

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On the uniform edge-partition of a tree
• Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches
• New Upper Bounds on Continuous Tree Edge-Partition Problem
• A note on the minimum bounded edge-partition of a tree
• A linear-time algorithm for finding an edge-partition with max-min ratio at most two

Cites work

• scientific article; zbMATH DE number 432817 (Why is no real title available?)
• A Linear Tree Partitioning Algorithm
• A Shifting Algorithm for Min-Max Tree Partitioning
• A shifting algorithm for continuous tree partitioning
• An algorithm for partitioning trees augmented with sibling edges
• Finding kth paths and p-centers by generating and searching good data structures
• Max-Min Tree Partitioning
• Most uniform path partitioning and its use in image processing
• New Upper Bounds on Continuous Tree Edge-Partition Problem
• On the uniform edge-partition of a tree
• Partitioning a Weighted Tree to Subtrees of Almost Uniform Size
• Shifting algorithms for tree partitioning with general weighting functions
• Spanning Trees and Optimization Problems

Cited in

(11)

• An overview of graph covering and partitioning
• New Upper Bounds on Continuous Tree Edge-Partition Problem
• A note on the minimum bounded edge-partition of a tree
• Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches
• Approximate envy-freeness in graphical cake cutting
• scientific article; zbMATH DE number 3866593 (Why is no real title available?)
• Tree edge decomposition with an application to minimum ultrametric tree approximation
• On a tree-cutting problem of P. Ash
• A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees
• A linear-time algorithm for finding an edge-partition with max-min ratio at most two
• On the uniform edge-partition of a tree

This page was built for publication: A tight bound on the min-ratio edge-partitioning problem of a tree

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