Naslov
Approximating k-hop Minimum Spanning Trees in Euclidean metrics

Autori
Laue, Soeren ; Matijević, Domagoj

Izvornik
Information processing letters (0020-0190) 107 (2008), 3-4; 96-101

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
approximation algorithms; minimum spanning trees; depth restriction

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA