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

DOI10.1016/J.DAM.2009.04.001MaRDI QIDQ967344zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmoptimization problempartitiontree

Mathematics Subject Classification ID

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

Recommendations

• New Upper Bounds on Continuous Tree Edge-Partition Problem
• A tight bound on the min-ratio edge-partitioning problem of a tree
• On the uniform edge-partition of a tree
• A shifting algorithm for constrained min-max partition on trees
• scientific article; zbMATH DE number 3866593

Cites work

• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• A 5/4 linear time bin packing algorithm
• A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree
• A linear time bin-packing algorithm
• Approximation algorithms for NP-hard problems.
• Exact solution of bin-packing problems using column generation and branch-and-bound
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• On the uniform edge-partition of a tree
• Scenarios for multistage stochastic programs

Cited in

(6)

• Minimum degree and minimum number of edge-disjoint trees
• On the uniform edge-partition of a tree
• scientific article; zbMATH DE number 3866593 (Why is no real title available?)
• A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees
• scientific article; zbMATH DE number 7310136 (Why is no real title available?)
• A tight bound on the min-ratio edge-partitioning problem of a tree

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

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