Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the relation between graph distance and Euclidean distance in random geometric graphs

Autor
Diaz, J.; Dieter, M.; Perarnau-Llobet, G.; Pérez-Giménez, X.
Tipus d'activitat
Article en revista
Revista
Advances in applied probability
Data de publicació
2016-09-01
Volum
48
Número
3
Pàgina inicial
848
Pàgina final
864
DOI
https://doi.org/10.1017/apr.2016.31 Obrir en finestra nova
URL
https://www.cambridge.org/core/journals/advances-in-applied-probability/article/div-classtitleon-the-relation-between-graph-distance-and-euclidean-distance-in-random-geometric-graphsdiv/2A5D7775A19265E42A8090A5ED981551 Obrir en finestra nova
Resum
Given any two vertices u, v of a random geometric graph G(n, r), denote by dE(u, v) their Euclidean distance and by dE(u, v) their graph distance. The problem of finding upper bounds on dG(u, v) conditional on dE(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=¿(vlogn) (that is, for r above the connectivity threshold). Our result also improves the best known estimates on the dia...
Paraules clau
Random Geometric Graph, Graph Distance, Euclidean Distance, Diameter
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions

Participants

  • Diaz Cort, Jose Maria  (autor)
  • Mitsche, Dieter Wilhelm  (autor)
  • Perarnau Llobet, Guillem  (autor)
  • Pérez Giménez, Xavier  (autor)