On the Expected Maximum Degree of Gabriel and Yao Graphs

Simple item page
dc.creatorDevroye, Luc
dc.creatorGudmundsson, Joachim
dc.creatorMorin, Pat
dc.date2009-05-21
dc.date.accessioned2026-07-07T13:17:31Z
dc.date.available2026-07-07T13:17:31Z
dc.descriptionMotivated 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.
dc.description20 pages, 10 figures
dc.identifierhttps://arxiv.org/abs/0905.3584
dc.identifierhttp://arxiv.org/abs/0905.3584
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/231137
dc.subjectComputational Geometry
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectI.3.5; E.1
dc.titleOn the Expected Maximum Degree of Gabriel and Yao Graphs
dc.typetext

Files

Collections

arXiv