On the total length of the random minimal directed spanning tree
From MaRDI portal
Publication:5480003
DOI10.1239/AAP/1151337075zbMATH Open1098.60046arXivmath/0409201OpenAlexW3106276570MaRDI QIDQ5480003FDOQ5480003
Authors: Mathew D. Penrose, Andrew R. Wade 
Publication date: 25 July 2006
Published in: Advances in Applied Probability (Search for Journal in Brave)
Abstract: In Bhatt and Roy's minimal directed spanning tree (MDST) 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 and 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 dominating. In the critical case where the weight is simple Euclidean length, both effects contribute significantly to the limit law. We also give a law of large numbers for the total weight of the graph.
Full work available at URL: https://arxiv.org/abs/math/0409201
Recommendations
- Rooted edges of a minimal directed spanning tree on random points
- Random minimal directed spanning trees and Dickman-type distributions
- Asymptotics for weighted minimal spanning trees on random points
- Asymptotics for Euclidean minimal spanning trees on random points
- Growth rates of Euclidean minimal spanning trees with power weighted edges
Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05)
Cites Work
- Central limit theorems for some graphs in computational geometry.
- Multivariate spatial central limit theorems with applications to percolation and spatial graphs
- Random Geometric Graphs
- Weak laws of large numbers in geometric probability
- Probability theory of classical Euclidean optimization problems
- Title not available (Why is that?)
- A general limit theorem for recursive algorithms and combinatorial structures
- The contraction method for recursive algorithms
- Asymptotic laws for nonconservative self-similar fragmentations
- On the Distribution of the Number of Admissible Points in a Vector Random Sample
- Title not available (Why is that?)
- Asymptotics of divide-and-conquer recurrences: Batcher's sorting algorithm and a minimum Euclidean matching heuristic
- A fixed point theorem for distributions
- The central limit theorem for weighted minimal spanning trees on random points
- Large deviation principles for Euclidean functionals and other nearly additive processes
- On a random directed spanning tree
- Rooted edges of a minimal directed spanning tree on random points
- Random minimal directed spanning trees and Dickman-type distributions
- Title not available (Why is that?)
Cited In (21)
- On a random directed spanning tree
- The 2D-directed spanning forest is almost surely a tree
- Explicit laws of large numbers for random nearest-neighbour-type graphs
- Random minimal directed spanning trees and Dickman-type distributions
- Rooted edges of a minimal directed spanning tree on random points
- The functional equation of the smoothing transform
- Linear stochastic equations in the critical case
- Laws of large numbers in stochastic geometry with statistical applications
- Traffic flow densities in large transport networks
- The radial spanning tree of a Poisson point process
- Asymptotic theory for the multidimensional random on-line nearest-neighbour graph
- A boundary corrected expansion of the moments of nearest neighbor distributions
- Fixed points of the smoothing transform: two-sided solutions
- Asymptotics of geometrical navigation on a random set of points in the plane
- Gaussian approximation for rooted edges in a random minimal directed spanning tree
- The smoothing transform: a review of contraction results
- Thin tails of fixed points of the nonhomogeneous smoothing transform
- The Dickman–Goncharov distribution
- Central limit theorems for the radial spanning tree
- The Expected Length of a Minimal Spanning Tree of a Cylinder Graph
- Limit theorems for random spatial drainage networks
Uses Software
This page was built for publication: On the total length of the random minimal directed spanning tree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5480003)
