Chain-constrained spanning trees

DOI10.1007/s10107-017-1126-7zbMath1386.68223OpenAlexW2592046007MaRDI QIDQ1702777

Neil Olver, Rico Zenklusen

Publication date: 28 February 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/26960

zbMATH Keywords

network designapproximation algorithmsspanning trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (1)

A Spectral Approach to Network Design

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On generalizations of network design problems with degree bounds
• A factor 2 approximation algorithm for the generalized Steiner network problem
• 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: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• 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
• A generalization of permanent inequalities and applications in counting and optimization
• Approximation algorithms for degree-constrained minimum-cost network-design problems

This page was built for publication: Chain-constrained spanning trees