Distributed spanner construction in doubling metric spaces.

This paper presents a distributed algorithm that runs on an n-node unit ball graph (UBG) G residing in a metric space of constant doubling dimension, and constructs, for any " > 0, a (1 + ")-spanner H of G with maximum degree bounded above by a constant. In addition, we show that H is \lightweight",...

Full description

Bibliographic Details
Main Authors: Damian, Mirela., Pandit, Saurav., Pemmaraju, Sriram.
Format: Villanova Faculty Authorship
Language:English
Published: 2006
Online Access:http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175665