On a random directed spanning tree
Authors:
- 1 March 2004
- journal article
- stochastic geometry-and-statistical-applications
- Published by Cambridge University Press (CUP) in Advances in Applied Probability
- Vol. 36 (01) , 19-42
Abstract
We study the asymptotic properties of a minimal spanning tree formed by n points uniformly distributed in the unit square, where the minimality is amongst all rooted spanning trees with a direction of growth. We show that the number of branches from the root of this tree, the total length of these branches, and the length of the longest branch each converges weakly. This model is related to the study of record values in the theory of extreme-value statistics and this relation is used to obtain our results. The results also hold when the tree is formed from a Poisson point process of intensity n in the unit square.Keywords
This publication has 8 references indexed in Scilit:
- On regular variation for infinitely divisible random vectors and additive processesAdvances in Applied Probability, 2006
- Chance and Stability1999
- The central limit theorem for weighted minimal spanning trees on random pointsThe Annals of Applied Probability, 1996
- Asymptotics for Euclidean minimal spanning trees on random pointsProbability Theory and Related Fields, 1992
- Growth Rates of Euclidean Minimal Spanning Trees with Power Weighted EdgesThe Annals of Probability, 1988
- A Course in Probability Theory1974
- Random Plane NetworksJournal of the Society for Industrial and Applied Mathematics, 1961
- The shortest path through many pointsMathematical Proceedings of the Cambridge Philosophical Society, 1959