A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees

DOI10.1137/S009753970036917XzbMath1008.68162OpenAlexW2063807274MaRDI QIDQ3149894

Publication date: 29 September 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753970036917x

zbMATH Keywords

Lagrangean relaxation approximation algorithms network algorithms spanning trees bicriteria approximation degree-bounded spanning trees

Mathematics Subject Classification ID

Trees (05C05) Multi-objective and goal programming (90C29) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (27)

Design and Analysis of Optimization Algorithms Using Computational Statistics ⋮ On approximating degree-bounded network design problems ⋮ A 2k-vertex Kernel for Maximum Internal Spanning Tree ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Partial degree bounded edge packing problem for graphs and \(k\)-uniform hypergraphs ⋮ On Lagrangian relaxation for constrained maximization and reoptimization problems ⋮ On generalizations of network design problems with degree bounds ⋮ Bounded-degree minimum-radius spanning trees in wireless sensor networks ⋮ Approximating directed weighted-degree constrained networks ⋮ Network design with weighted degree constraints ⋮ Chain-constrained spanning trees ⋮ Approximating Directed Weighted-Degree Constrained Networks ⋮ The Maximum Binary Tree Problem. ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ Budgeted matching and budgeted matroid intersection via the gasoline puzzle ⋮ On approximating degree-bounded network design problems ⋮ On Lagrangian Relaxation and Subset Selection Problems ⋮ Network Design with Weighted Degree Constraints ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ The maximum binary tree problem ⋮ Approximating MIN-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems ⋮ Degree-bounded minimum spanning trees ⋮ A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids ⋮ Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal ⋮ Electrical flows over spanning trees ⋮ Unnamed Item

This page was built for publication: A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees