ON THE RELATION BETWEEN GRAPH DISTANCE AND EUCLIDEAN DISTANCE IN RANDOM GEOMETRIC GRAPHS

Abstract : Given any two vertices u, v of a random geometric graph G(n, r), denote by d_E(u, v) their Euclidean distance and by d_G(u, v) their graph distance. The problem of finding upper bounds on d_G(u, v) conditional on d_E(u, v) that hold asymptotically almost surely has received quite a bit of attention in the literature. In this paper, we improve the known upper bounds for values of r = \omega\sqrt(log n)) (i.e. for r above the connectivity threshold). Our result also improves the best known estimates on the diameter of random geometric graphs. We also provide a lower bound on d_G(u, v) conditional on d_E(u, v).
Type de document :
Article dans une revue
Advances in Applied Probability, Applied Probability Trust, 2016
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01291932
Contributeur : Dieter Mitsche <>
Soumis le : mardi 22 mars 2016 - 12:23:03
Dernière modification le : mercredi 10 octobre 2018 - 21:36:02
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 22:44:41

Fichier

distancies-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01291932, version 1

Collections

Citation

Josep Diaz, Dieter Mitsche, Guillem Perarnau, Xavier Pérez-Giménez. ON THE RELATION BETWEEN GRAPH DISTANCE AND EUCLIDEAN DISTANCE IN RANDOM GEOMETRIC GRAPHS. Advances in Applied Probability, Applied Probability Trust, 2016. 〈hal-01291932〉

Partager

Métriques

Consultations de la notice

80

Téléchargements de fichiers

35