文章基本信息

标题：Traveling in Randomly Embedded Random Graphs
本地全文：下载
作者：Alan Frieze ; Wesley Pegden
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：81
页码：45:1-45:17
DOI：10.4230/LIPIcs.APPROX-RANDOM.2017.45
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Traveling Salesman; Euclidean; Shortest Path