Document Open Access Logo

Traveling in Randomly Embedded Random Graphs

Authors Alan Frieze, Wesley Pegden

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.45.pdf
  • Filesize: 0.54 MB
  • 17 pages

Document Identifiers

Author Details

Alan Frieze
Wesley Pegden

Cite As Get BibTex

Alan Frieze and Wesley Pegden. Traveling in Randomly Embedded Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 45:1-45:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.45

Abstract

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.

Subject Classification

Keywords
  • Traveling Salesman
  • Euclidean
  • Shortest Path

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Beardwood, J. H. Halton, and J. M. Hammersley. The shortest path through many points. Mathematical Proceedings of the Cambridge Philosophical Society, 55:299-327, 1959. Google Scholar
  2. B. Bollobás. Random Graphs, Second Edition. Cambridge University Press, 2001. Google Scholar
  3. B. Bollobás, T. Fenner, and A. M. Frieze. An algorithm for finding hamilton paths and cycles in random graphs. Combinatorica, 7:327-341, 1987. Google Scholar
  4. D. Fernholz and V. Ramachandran. The diameter of sparse random graphs. Random Structures and Algorithms, 31:482-516, 2007. Google Scholar
  5. Y. Gurevich and S. Shelah. Expected computation time for hamiltonian path problem. SIAM Journal on Computing, 16:486-502, 1987. Google Scholar
  6. R. M. Karp. Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Mathematics of Operations Research, 2:209-244, 1977. Google Scholar
  7. A. Mehrabian. A randomly embedded random graph is not a spanner. In Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), pages 373-374, 2011. Google Scholar
  8. A. Mehrabian and N. Wormald. On the stretch factor of randomly embedded random graphs. Discrete &Computational geometry, 49:647-658, 2013. Google Scholar
  9. P. M. Penrose. Random Geometric Graphs. Oxford University Press, 2003. Google Scholar
  10. W. Rhee and M. Talagrand. A sharp deviation inequality for the stochastic traveling salesman problem. The Annals of Probability, 17:1-8, 1989. Google Scholar
  11. O. Riordan and N. Wormald. The diameter of sparse random graphs. Combinatorics, Probability and Computing, 19:835-926, 2010. Google Scholar
  12. J. M. Steele. Subadditive euclidean functionals and nonlinear growth in geometric probability. The Annals of Probability, 9:365-376, 1981. Google Scholar
  13. J. Yukich. Probability Theory of Classical Euclidean Optimization Problems. Springer, 1991. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact