Luc Devroye ; Linda Farczadi - Connectivity for line-of-sight networks in higher dimensions

dmtcs:610 - Discrete Mathematics & Theoretical Computer Science, May 15, 2013, Vol. 15 no. 2 - https://doi.org/10.46298/dmtcs.610
Connectivity for line-of-sight networks in higher dimensionsArticle

Authors: Luc Devroye ; Linda Farczadi 1

  • 1 Department of Combinatorics and Optimization

Let T be a d-dimensional toroidal grid of n^d points. For a given range parameter ω, and a positive integer k ≤q d, we say that two points in T are mutually visible if they differ in at most k coordinates and are a distance at most ω apart, where distance is measured using the \ellₚ norm. We obtain a random d-dimensional line-of-sight graph G by placing a node at each point in T independently with some fixed probability p^* and connecting all pairs of mutually visible nodes. We prove an asymptotically tight connectivity result for this random graph.


Volume: Vol. 15 no. 2
Section: Analysis of Algorithms
Published on: May 15, 2013
Accepted on: June 9, 2015
Submitted on: December 13, 2010
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

1 Document citing this article

Consultation statistics

This page has been seen 330 times.
This article's PDF has been downloaded 404 times.