engleski

Approximating k-hop Minimum Spanning Trees in Euclidean metrics

In the minimum-cost $k$-hop spanning tree ($k$-hop MST) problem, we are given a set $S$ of $n$ points in a metric space, a positive small integer $k$ and a root point $r\in S$. We are interested in computing a rooted spanning tree of minimum cost such that the longest root-leaf path in the tree has at most $k$ edges. We present a polynomial- time approximation scheme for the plane. Our algorithms is based on Arora's at el. techniques for the Euclidean $k$-median problem.

approximation algorithms; minimum spanning trees; depth restriction

nije evidentirano