Skip to main content

Research Repository

Advanced Search

On the total length of the random minimal directed spanning tree

Penrose, Mathew D.; Wade, Andrew R.

On the total length of the random minimal directed spanning tree Thumbnail


Authors

Mathew D. Penrose



Abstract

In Bhatt and Roy's minimal directed spanning tree 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 plus 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 being dominant. In the critical case in which the weight is simple Euclidean length, both effects contribute significantly to the limit law.

Citation

Penrose, M. D., & Wade, A. R. (2006). On the total length of the random minimal directed spanning tree. Advances in Applied Probability, 38(2), 336-372. https://doi.org/10.1239/aap/1151337075

Journal Article Type Article
Publication Date Jan 1, 2006
Deposit Date Oct 4, 2012
Publicly Available Date Mar 29, 2024
Journal Advances in Applied Probability
Print ISSN 0001-8678
Electronic ISSN 1475-6064
Publisher Applied Probability Trust
Peer Reviewed Peer Reviewed
Volume 38
Issue 2
Pages 336-372
DOI https://doi.org/10.1239/aap/1151337075
Keywords Spanning tree, Nearest-neighbour graph, Weak convergence, Fixed-point equation, Phase transition, Fragmentation process.

Files




You might also like



Downloadable Citations