Technical Reports
 

Document Type

Article

Publication Date

3-2008

Comments

TR08-002

Abstract

We consider the problem of computing bounded-degree lightweight plane spanning subgraphs of unit disk graphs in the local distributed model of computation. We are motivated by the hypothesis that such subgraphs can provide the underlying network topology for efficient unicasting and/or multicasting in wireless distributed systems. We start by showing that, for any integer $k \geq 2$, there exists a $k$-local distributed algorithm that, given a unit disk graph $U$ embedded in the plane, constructs a plane subgraph of $U$ containing a Euclidean Minimum Spanning Tree (EMST) of $V(U)$, whose degree is at most 6, and whose total weight is at most $(1 + \frac{2}{k-1})$ times the weight of an EMST of $V(U)$. We show that this bound is tight by proving that, for any $\epsilon > 0$, there exists a unit disk graph $U$ such that no $k$-local distributed algorithm can construct a spanning subgraph of $U$ whose total weight is at most $(1 + \frac{2}{k-1} -\epsilon)$ times the weight of an EMST of $V(U)$. We then go further and present the first $k$-local distributed algorithm, where $k$ is a constant, that computes a bounded-degree plane lightweight {\em spanner} of a given unit disk graph. The upper bounds on the number of communication rounds of the algorithm, the degree, the stretch factor, and the weight of the spanner, are very small. For example, our results imply an $18$-local distributed algorithm that computes a plane spanner of a given unit disk graph $U$, whose degree is at most 14, stretch factor at most 8.81, and weight at most $8.81$ times the weight of an EMST of $V(U)$.

All the obtained results rely on an elegant structural result that we develop for weighted planar graphs. We show a wider application of this result by giving an $O(n\lg{n})$ time centralized algorithm that constructs bounded-degree plane lightweight spanners of unit disk graphs (which include Euclidean graphs), with the best upper bounds on the spanner degree, stretch factor, and weight.

Download

Share

COinS