Mathematics – Probability
Scientific paper
2004-09-13
Shorter version published in Advances in Applied Probability, Vol. 38 (2006), no. 2, p. 336-372
Mathematics
Probability
58 Pages, 6 figures (2 colour)
Scientific paper
10.1239/aap/1151337075
In Bhatt and Roy's minimal directed spanning tree (MDST) construction for a random partially ordered set of points in the unit square,all edges must respect the ``coordinatewise'' partial order and there must be a directed path from each vertex to a minimal element. We study the asymptotic behaviour of the total length of this graph with power weighted edges. The limiting distribution is given by the sum of a normal component away from the boundary and a contribution introduced by the boundary effects, which can be characterized by a fixed point equation, and is reminiscent of limits arising in the probabilistic analysis of certain algorithms. As the exponent of the power weighting increases, the distribution undergoes a phase transition from the normal contribution being dominant to the boundary effects dominating. In the critical case where the weight is simple Euclidean length, both effects contribute significantly to the limit law. We also give a law of large numbers for the total weight of the graph.
Penrose Mathew D.
Wade Andrew R.
No associations
LandOfFree
On the total length of the random minimal directed spanning tree 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 On the total length of the random minimal directed spanning tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the total length of the random minimal directed spanning tree will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-530830