A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
From MaRDI portal
Publication:3613760
DOI10.1007/11786986_18zbMath1223.68126OpenAlexW2159156348MaRDI QIDQ3613760
No author found.
Publication date: 12 March 2009
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11786986_18
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (8)
Spanning trees with minimum weighted degrees ⋮ What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs ⋮ Approximating directed weighted-degree constrained networks ⋮ Approximating Directed Weighted-Degree Constrained Networks ⋮ An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem ⋮ Budgeted matching and budgeted matroid intersection via the gasoline puzzle ⋮ Network Design with Weighted Degree Constraints ⋮ A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids
This page was built for publication: A Push-Relabel Algorithm for Approximating Degree Bounded MSTs
