Localized Spanners for Wireless Networks

Mirela Damian; Sriram V Pemmaraju

doi:10.48550/arxiv.0806.4221

Back

Localized Spanners for Wireless Networks

Preprint

Open access

Localized Spanners for Wireless Networks

Mirela Damian and Sriram V Pemmaraju

ArXiv.org

06/25/2008

DOI: 10.48550/arxiv.0806.4221

Files and links (1)

url

https://doi.org/10.48550/arXiv.0806.4221View

Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

We present a new efficient localized algorithm to construct, for any given quasi-unit disk graph G=(V,E) and any e > 0, a (1+e)-spanner for G of maximum degree O(1) and total weight O(w(MST)), where w(MST) denotes the weight of a minimum spanning tree for V. We further show that similar localized techniques can be used to construct, for a given unit disk graph G = (V, E), a planar Cdel(1+e)(1+pi/2)-spanner for G of maximum degree O(1) and total weight O(w(MST)). Here Cdel denotes the stretch factor of the unit Delaunay triangulation for V. Both constructions can be completed in O(1) communication rounds, and require each node to know its own coordinates.

Computer Science - Distributed, Parallel, and Cluster Computing

Details

Title: Subtitle: Localized Spanners for Wireless Networks
Creators: Mirela Damian
Sriram V Pemmaraju
Resource Type: Preprint
Publication Details: ArXiv.org
DOI: 10.48550/arxiv.0806.4221
ISSN: 2331-8422
Language: English
Date posted: 06/25/2008
Academic Unit: Computer Science
Record Identifier: 9984411090702771

Metrics

1 Record Views