A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids

DOI10.1016/j.tcs.2009.07.029zbMath1205.68509OpenAlexW2083383617MaRDI QIDQ1035684

J. Blot

Publication date: 4 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.029

zbMATH Keywords

approximation algorithmsspanning treesdegree-bounded network designpush-relabel

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (11)

A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ On generalizations of network design problems with degree bounds ⋮ Network design with weighted degree constraints ⋮ Chain-constrained spanning trees ⋮ Refuting a conjecture of goemans on bounded degree spanning trees ⋮ Degree bounded matroids and submodular flows ⋮ The Maximum Binary Tree Problem. ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ The maximum binary tree problem ⋮ Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Degree-bounded minimum spanning trees
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
• On two geometric problems related to the travelling salesman problem
• Degree Bounded Matroids and Submodular Flows
• Survivable network design with degree or order constraints
• Approximating minimum bounded degree spanning trees to within one of optimal
• Primal-dual meets local search
• Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs
• A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Low-Degree Spanning Trees of Small Weight
• Euclidean bounded-degree spanning tree ratios
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids