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

DOI10.1016/J.DAM.2010.05.014zbMath1215.05030OpenAlexW2060058676MaRDI QIDQ608252

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

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

treepartitionalgorithmoptimization problem

Mathematics Subject Classification ID

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

Related Items (2)

An overview of graph covering and partitioning ⋮ A linear-time algorithm for finding an edge-partition with max-min ratio at most two

Cites Work

• Unnamed Item
• An algorithm for partitioning trees augmented with sibling edges
• Most uniform path partitioning and its use in image processing
• A shifting algorithm for continuous tree partitioning
• On the uniform edge-partition of a tree
• New Upper Bounds on Continuous Tree Edge-Partition Problem
• Partitioning a Weighted Tree to Subtrees of Almost Uniform Size
• Shifting algorithms for tree partitioning with general weighting functions
• Max-Min Tree Partitioning
• A Shifting Algorithm for Min-Max Tree Partitioning
• A Linear Tree Partitioning Algorithm
• Spanning Trees and Optimization Problems
• Finding kth paths and p-centers by generating and searching good data structures

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