On the Expected Maximum Degree of Gabriel and Yao Graphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Motivated by applications of Gabriel graphs and Yao graphs in wireless ad-hoc networks, we show that the maximal degree of a random Gabriel graph or Yao graph defined on $n$ points drawn uniformly at random from a unit square grows as $Θ(\log n / \log \log n)$ in probability.
20 pages, 10 figures

Keywords

Computational Geometry, Distributed, Parallel, and Cluster Computing, I.3.5; E.1

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/231137

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0905.3584
 http://arxiv.org/abs/0905.3584

Collections

arXiv