10.1184/R1/6480137.v1
Alan Frieze
Alan
Frieze
Wesley Pegden
Wesley
Pegden
Traveling in randomly embedded random graphs
Carnegie Mellon University
2014
Mathematical Sciences
2014-11-24 00:00:00
Journal contribution
https://kilthub.cmu.edu/articles/journal_contribution/Traveling_in_randomly_embedded_random_graphs/6480137
<p>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.</p>