Abstract
For a complete graph of size , assign each edge an i.i.d.\ exponential variable with mean . For , consider the length of the longest path whose average weight is at most . It was shown by Aldous (1998) that the length is of order for and of order for . In this paper, we study the near-supercritical regime where with a small fixed number. We show that there exist two absolute constants such that with high probability the length is in between and . Our result corrects a non-rigorous prediction of Aldous (2005).
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.