Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs

Emmett Breen, Renee Mirka, Zichen Wang +1

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 span…