Edgar A. Ramos,
Given a complete graph on~n nodes with metric edge costs, the
minimum-cost $k$-hop spanning tree (\khmst) problem
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.