A note on the minimum bounded edge-partition of a tree

DOI10.1016/J.DAM.2009.04.001zbMath1211.05024OpenAlexW1987374081MaRDI QIDQ967344

Shane Dye

Publication date: 28 April 2010

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

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

zbMATH Keywords

treepartitionapproximation algorithmoptimization problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• A linear time bin-packing algorithm
• Exact solution of bin-packing problems using column generation and branch-and-bound
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• A faster 2-approximation algorithm for the minmax \(p\)-traveling salesmen problem on a tree
• A 5/4 linear time bin packing algorithm
• On the uniform edge-partition of a tree
• Scenarios for multistage stochastic programs

This page was built for publication: A note on the minimum bounded edge-partition of a tree