Revisiting Garg's 2-Approximation Algorithm for the <i>k</i>-MST Problem in Graphs
Revisiting Garg's 2-Approximation Algorithm for the <i>k</i>-MST Problem in Graphs
This paper revisits the 2-approximation algorithm for $k$-MST presented by Garg in light of a recent paper of Paul et al.. In the $k$-MST problem, the goal is to return a tree spanning $k$ vertices of minimum total edge cost. Paul et al. extend Garg's primal-dual subroutine to improve the …