Bounded-degree minimum-radius spanning trees in wireless sensor networks

In this paper, we study the problem of computing a spanning tree of a given undirected disk graph such that the radius of the tree is minimized subject to a given degree constraint Δ⁎. We first introduce an (8,4)-bicriteria approximation algorithm for unit disk graphs (which is a special case of disk graphs) that computes a spanning tree such that the degree of any nodes in the tree is at most Δ⁎+8 and its radius is at most 4⋅OPT, where OPT is the minimum possible radius of any spanning tree with degree bound Δ⁎. We also introduce an (α,2)-bicriteria approximation algorithm for disk graphs that computes a spanning tree whose maximum node degree is at most Δ⁎+α and whose radius is bounded by 2⋅OPT, where α is a non-constant value that depends on M and k with M being the number of distinct disk radii and k being the ratio of the largest and the smallest disk radius.