# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Approximating k-Hop Minimum-Spanning Trees

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Althaus, E., Funke, S., Har-Peled, S., Könemann, J., Ramos, E. A., & Skutella, M. (2005).
Approximating k-Hop Minimum-Spanning Trees.* Operations Research Letters,* *33*,
115-120.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-25C1-0

##### Abstract

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.