On the total length of the random minimal directed spanning tree
Penrose, M.D. and Wade, Andrew (2006) On the total length of the random minimal directed spanning tree. Advances in Applied Probability, 38 (2). pp. 336372. ISSN 00018678 (https://doi.org/10.1239/aap/1151337075)
Full text not available in this repository.Request a copyAbstract
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 powerweighted 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 fixedpoint 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.


Item type: Article ID code: 34460 Dates: DateEventJune 2006PublishedKeywords: spanning tree, nearestneighbour graph, weak convergence, fixedpoint equation, phase transition, fragmentation process, Probabilities. Mathematical statistics, Applied Mathematics, Statistics and Probability Subjects: Science > Mathematics > Probabilities. Mathematical statistics Department: Faculty of Science > Mathematics and Statistics Depositing user: Pure Administrator Date deposited: 04 Nov 2011 12:52 Last modified: 03 Feb 2023 10:13 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/34460