A Simple Yao-Yao-Based Spanner of Bounded Degree

Details A Simple Yao-Yao-Based Spanner of Bounded Degree A Simple Yao-Yao-Based Spanner of Bounded Degree

2008-02-29

arxiv.org/abs/0802.4325v2

Computer Science

Computational Geometry

7 pages, 5 figures

Scientific paper

It is a standing open question to decide whether the Yao-Yao structure for unit disk graphs (UDGs) is a length spanner of not. This question is highly relevant to the topology control problem for wireless ad hoc networks. In this paper we make progress towards resolving this question by showing that the Yao-Yao structure is a length spanner for UDGs of bounded aspect ratio. We also propose a new local algorithm, called Yao-Sparse-Sink, based on the Yao-Sink method introduced by Li, Wan, Wang and Frieder, that computes a (1+e)-spanner of bounded degree for a given UDG and for given e > 0. The Yao-Sparse-Sink method enables an efficient local computation of sparse sink trees. Finally, we show that all these structures for UDGs -- Yao, Yao-Yao, Yao-Sink and Yao-Sparse-Sink -- have arbitrarily large weight.

Affiliated with

Also associated with

No associations

Rating

A Simple Yao-Yao-Based Spanner of Bounded Degree does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Simple Yao-Yao-Based Spanner of Bounded Degree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Simple Yao-Yao-Based Spanner of Bounded Degree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-352692