On the Critical Value for 'Percolation' of Minimum-Weight Trees in the Mean-Field Distance Model
- Author(s): Aldous, D
- et al.
Published Web Locationhttps://doi.org/10.1017/S0963548397003155
Consider the complete n-graph with independent exponential (mean n) edge-weights. Let M(c, n) be the maximal size of subtree for which the average edge-weight is at most c. It is shown that M(c, n) makes the transition from o(n) to Ω(n) around some critical value c(0), which can be specified in terms of a fixed point of a mapping on probability distributions.
Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.