On the total length of the random minimal directed spanning tree

M.D. Penrose, Andrew Wade

Research output: Contribution to journalArticle

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.
LanguageEnglish
Pages336-372
Number of pages37
JournalAdvances in Applied Probability
Volume38
Issue number2
DOIs
Publication statusPublished - Jun 2006

Fingerprint

Boundary Effect
Spanning tree
Probabilistic Analysis of Algorithms
Phase transitions
Fixed-point Equation
Limit Laws
Critical Case
Partially Ordered Set
Partial Order
Limiting Distribution
Set of points
Weighting
Euclidean
Phase Transition
Asymptotic Behavior
Exponent
Path
Unit
Graph in graph theory
Vertex of a graph

Keywords

  • spanning tree
  • nearest-neighbour graph
  • weak convergence
  • fixed-point equation
  • phase transition
  • fragmentation process

Cite this

Penrose, M.D. ; Wade, Andrew. / On the total length of the random minimal directed spanning tree. In: Advances in Applied Probability. 2006 ; Vol. 38, No. 2. pp. 336-372.
@article{267b5e5826784392bb1675386cdefb9c,
title = "On the total length of the random minimal directed spanning tree",
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.",
keywords = "spanning tree, nearest-neighbour graph, weak convergence, fixed-point equation, phase transition, fragmentation process",
author = "M.D. Penrose and Andrew Wade",
year = "2006",
month = "6",
doi = "10.1239/aap/1151337075",
language = "English",
volume = "38",
pages = "336--372",
journal = "Advances in Applied Probability",
issn = "0001-8678",
number = "2",

}

On the total length of the random minimal directed spanning tree. / Penrose, M.D.; Wade, Andrew.

In: Advances in Applied Probability, Vol. 38, No. 2, 06.2006, p. 336-372.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the total length of the random minimal directed spanning tree

AU - Penrose, M.D.

AU - Wade, Andrew

PY - 2006/6

Y1 - 2006/6

N2 - 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.

AB - 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.

KW - spanning tree

KW - nearest-neighbour graph

KW - weak convergence

KW - fixed-point equation

KW - phase transition

KW - fragmentation process

UR - http://projecteuclid.org/euclid.aap/1151337075

UR - http://arxiv.org/abs/math/0409201

U2 - 10.1239/aap/1151337075

DO - 10.1239/aap/1151337075

M3 - Article

VL - 38

SP - 336

EP - 372

JO - Advances in Applied Probability

T2 - Advances in Applied Probability

JF - Advances in Applied Probability

SN - 0001-8678

IS - 2

ER -