Approximating k-hop Minimum Spanning Trees
Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Koenemann, Edgar Ramos, Martin Skutella
In this paper we consider the problem of computing minimum-cost
spanning trees with depth restrictions. Specifically, we are given
an $n$-node complete graph $G$, a metric cost-function $c$ on its
edges, and an integer $k\geq 1$. The goal in the minimum-cost
$k$-hop spanning tree problem is to compute a spanning tree $T$
in $G$ of minimum total cost such that the longest root-leaf-path
in the tree has at most $k$ edges.
Our main result is an algorithm that computes a tree of depth at
most $k$ and total expected cost $O(\log n)$ times that of a
minimum-cost $k$-hop spanning-tree. The result is based upon earlier
work on metric space approximation due to Fakcharoenphol et
al.[FRT03] and Bartal [Bart96,Bart98]. In particular we
show that the problem can be solved exactly in polynomial
time when the cost metric $c$ is induced by a so-called
hierarchically well-separated tree.
PDF