Refuting a conjecture of goemans on bounded degree spanning trees

DOI10.1016/j.orl.2016.09.014zbMath1408.90294OpenAlexW2529324002WikidataQ123224189 ScholiaQ123224189MaRDI QIDQ1709958

Rico Zenklusen, Stephen R. Chestnut, Martin Nägele

Publication date: 15 January 2019

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2016.09.014

zbMATH Keywords

approximation algorithmmatroidbounded degree spanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05)

Cites Work

• Unnamed Item
• On generalizations of network design problems with degree bounds
• A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
• Approximating MIN-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs
• A matter of degree
• Approximating minimum bounded degree spanning trees to within one of optimal
• Primal-dual meets local search
• Additive Guarantees for Degree-Bounded Directed Network Design
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Chain-Constrained Spanning Trees
• Many birds with one stone
• Approximation algorithms for degree-constrained minimum-cost network-design problems

This page was built for publication: Refuting a conjecture of goemans on bounded degree spanning trees