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

DOI10.1016/j.tcs.2009.07.029zbMath1205.68509MaRDI 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 algorithms; spanning trees; degree-bounded network design; push-relabel

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms