Loading...
Loading...

Go to the content (press return)

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

Author
Diaz, J.; Dieter, M.; Perarnau-Llobet, G.; Pérez-Giménez, X.
Type of activity
Journal article
Journal
Advances in applied probability
Date of publication
2016-09-01
Volume
48
Number
3
First page
848
Last page
864
DOI
https://doi.org/10.1017/apr.2016.31 Open in new window
Repository
http://hdl.handle.net/2117/115054 Open in new window
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 Open in new window
Abstract
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...
Citation
Diaz, J., Dieter, M., Perarnau-Llobet, G., Pérez-Giménez, X. On the relation between graph distance and Euclidean distance in random geometric graphs. "Advances in applied probability", 1 Setembre 2016, vol. 48, núm. 3, p. 848-864.
Keywords
Euclidean distance, Random geometric graph, diameter, graph distance
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants

Attachments