On the total length of the random minimal directed spanning tree

MD Penrose, AR Wade

Research output: Contribution to journalArticle (Academic Journal)

20 Citations (Scopus)

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.
Translated title of the contributionOn the total length of the random minimal directed spanning tree
Original languageEnglish
Pages (from-to)336 - 372
Number of pages37
JournalAdvances in Applied Probability
Volume38 (2)
DOIs
Publication statusPublished - Jun 2006

Bibliographical note

Publisher: Applied Probability Trust

Fingerprint Dive into the research topics of 'On the total length of the random minimal directed spanning tree'. Together they form a unique fingerprint.

Cite this