file.pdf (430.78 kB)
0/0

Traveling in randomly embedded random graphs

Download (430.78 kB)
journal contribution
posted on 24.11.2014 by Alan Frieze, Wesley Pegden

We consider the problem of traveling among random points in Euclidean space, when only a random fraction of the pairs are joined by traversable connections. In particular, we show a threshold for a pair of points to be connected by a geodesic of length arbitrarily close to their Euclidean distance, and analyze the minimum length Traveling Salesperson Tour, extending the Beardwood-Halton-Hammersley theorem to this setting.

History

Date

24/11/2014

Exports

Exports