Given an edge-weighted graph G = (V;E) and a sub- set 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 present a 20-approximation algorithm for the full Steiner tree problem when G is a unit disk graph.

Additional Metadata
Conference 26th Canadian Conference on Computational Geometry, CCCG 2014
Citation
Biniaz, A. (Ahmad), Maheshwari, A, & Smid, M. (2014). Approximating full steiner tree in a unit disk graph. Presented at the 26th Canadian Conference on Computational Geometry, CCCG 2014.