Traveling in randomly embedded random graphs
Traveling in randomly embedded random graphs
复制标题
在随机嵌入的随机图中旅行
DOI：
10.1002/rsa.20832
复制
发表时间：
2014
影响因子：
1
通讯作者：
W. Pegden
中科院分区：
文献类型：
--
作者：
A. Frieze;W. Pegden
我们考虑在欧几里得空间中随机点之间的行进问题，当对遍布的连接尤其是随机分数时，我们显示了一个由任意接近的地理位置连接的阈值他们的欧几里得距离，分析了最小长度的旅行销售人员之旅，将Beardwood -Halton -Hammersley定理扩展到了此环境。
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.