THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS

DOI10.1017/S0269964821000115zbMath1504.05259arXiv1912.13175OpenAlexW3146251037MaRDI QIDQ5051225

David J. Aldous

Publication date: 22 November 2022

Published in: Probability in the Engineering and Informational Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1912.13175

zbMATH Keywords

random graphmetric entropynearest neighbordeterministic walknearest unvisited vertex

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27) Processes in random environments (60K37)

Related Items (1)

Exploring Endless Space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the greedy walk problem
• Cover times, blanket times, and majorizing measures
• On the nearest neighbor rule for the metric traveling salesman problem
• The mean field traveling salesman and related problems
• On the value of a random minimum spanning tree problem
• Cost of sequential connection for points in space
• Probability theory of classical Euclidean optimization problems
• On the nearest neighbor rule for the traveling salesman problem
• The central limit theorem for weighted minimal spanning trees on random points
• Recurrence of distributional limits of finite planar graphs
• Online graph exploration: New results on old and new algorithms
• Weak Concentration for First Passage Percolation Times on Graphs and General Increasing Set-valued Processes
• 50 Years of First-Passage Percolation
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• First Passage Percolation on Random Geometric Graphs and an Application to Shortest-Path Trees
• Exploring Endless Space

This page was built for publication: THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS