file.pdf (430.78 kB)
Download file

Traveling in randomly embedded random graphs

Download (430.78 kB)
journal contribution
posted on 24.11.2014, 00:00 by Alan FriezeAlan 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.




Usage metrics