A PTAS for $k$-hop MST on the Euclidean plane: Improving Dependency on $k$

Jittat Fakcharoenphol, Nonthaphat Wongwattanakij

For any $\epsilon >0$, Laue and Matijević [CCCG'07, IPL'08] give a PTAS for finding a $(1+\epsilon )$-approximate solution to the $k$-hop MST problem in the Euclidean plane that runs in time $(n/ε…