On the total length of the random minimal directed spanning tree

Mathematics – Probability

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-530830

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.