Connectivity for line-of-sight networks in higher dimensions

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.71--86
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00980756
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 18 avril 2014 - 16:43:35
Dernière modification le : jeudi 7 septembre 2017 - 01:03:46
Document(s) archivé(s) le : lundi 10 avril 2017 - 15:31:52

Fichier

1784-7886-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00980756, version 1

Collections

Citation

Luc Devroye, Linda Farczadi. Connectivity for line-of-sight networks in higher dimensions. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.71--86. 〈hal-00980756〉

Partager

Métriques

Consultations de la notice

668

Téléchargements de fichiers

98