Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models

Details Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models

2006-09-20

arxiv.org/abs/math/0609547v2

Mathematics

Probability

24 pages, 3 figures

Scientific paper

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 $\delta$ 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 + \Theta(\delta^2)$. We prove this scaling result in the model of the lattice with random edge-lengths and in the Euclidean model.

Affiliated with

Also associated with

No associations

Rating

Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Near-Minimal Spanning Trees: a Scaling Exponent in Probability Models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-351444