Ernst Althaus,
Stefan Funke,
Sariel Har-Peled,
Jochen Konemann,
Edgar A. Ramos,
and
Martin Skutella
Given a complete graph on~n nodes with metric edge costs, the
minimum-cost $k$-hop spanning tree (\khmst) problem
asks for
a spanning tree of minimum total cost such that the longest
root-leaf-path in the tree has at most~$k$ edges. We present an
algorithm that computes such a tree of total expected cost O(log
n) times that of a minimum-cost $k$-hop spanning-tree.