Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

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

Penrose, Mathew D. and Wade, Andrew R. (2006) 'On the total length of the random minimal directed spanning tree.', Advances in applied probability., 38 (2). pp. 336-372.

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.

Item Type:Article
Keywords:Spanning tree, Nearest-neighbour graph, Weak convergence, Fixed-point equation, Phase transition, Fragmentation process.
Full text:(AM) Accepted Manuscript
Download PDF
(448Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1239/aap/1151337075
Date accepted:No date available
Date deposited:13 February 2013
Date of first online publication:2006
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar