On full Steiner trees in unit disk graphs
Given an edge-weighted graph G=(V,E) and a subset R of V, a Steiner tree of G is a tree which spans all the vertices in R. A full Steiner tree is a Steiner tree which has all the vertices of R as its leaves. The full Steiner tree problem is to find a full Steiner tree of G with minimum weight. In this paper we consider the full Steiner tree problem when G is a unit disk graph. We present a 20-approximation algorithm for the full Steiner tree problem in G. As for λ-precise unit disk graphs we present a (10+1λ)-approximation algorithm, where λ is the length of the shortest edge in G.
|Keywords||Approximation algorithms, Full, Steiner tree, Unit disk graph|
Biniaz, A. (Ahmad), Maheshwari, A, & Smid, M. (2015). On full Steiner trees in unit disk graphs. Computational Geometry, 48(6), 453–458. doi:10.1016/j.comgeo.2015.02.004