Page 1

Displaying 1 – 3 of 3

Showing per page

Near-minimal spanning trees : a scaling exponent in probability models

David J. Aldous, Charles Bordenave, Marc Lelarge (2008)

Annales de l'I.H.P. Probabilités et statistiques

We study the relation between the minimal spanning tree (MST) on many random points and the “near-minimal” tree which is optimal subject to the constraint that a proportion δ of its edges must be different from those of the MST. Heuristics suggest that, regardless of details of the probability model, the ratio of lengths should scale as 1+Θ(δ2). We prove this scaling result in the model of the lattice with random edge-lengths and in the euclidean model.

Non-hyperbolicity in random regular graphs and their traffic characteristics

Gabriel Tucci (2013)

Open Mathematics

In this paper we prove that random d-regular graphs with d ≥ 3 have traffic congestion of the order O(n logd−13 n) where n is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically δ-hyperbolic for any non-negative δ almost surely as n → ∞.

Currently displaying 1 – 3 of 3

Page 1