On the total length of the random minimal directed spanning tree

DOI10.1239/AAP/1151337075MaRDI QIDQ5480003zbMATH OpenOpenAlexFDO

Authors Mathew D. Penrose, Andrew R. Wade

Publication date 25 July 2006

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0409201

zbMATH Keywords

phase transitionpoint processspanning treefixed-point equationnearest-neighbour graph

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05)

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.

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

Cites work

• scientific article; zbMATH DE number 2038750 (Why is no real title available?)
• scientific article; zbMATH DE number 227027 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• A fixed point theorem for distributions
• A general limit theorem for recursive algorithms and combinatorial structures
• Asymptotic laws for nonconservative self-similar fragmentations
• Asymptotics of divide-and-conquer recurrences: Batcher's sorting algorithm and a minimum Euclidean matching heuristic
• Central limit theorems for some graphs in computational geometry.
• Large deviation principles for Euclidean functionals and other nearly additive processes
• Multivariate spatial central limit theorems with applications to percolation and spatial graphs
• On a random directed spanning tree
• On the Distribution of the Number of Admissible Points in a Vector Random Sample
• Probability theory of classical Euclidean optimization problems
• Random Geometric Graphs
• Random minimal directed spanning trees and Dickman-type distributions
• Rooted edges of a minimal directed spanning tree on random points
• The central limit theorem for weighted minimal spanning trees on random points
• The contraction method for recursive algorithms
• Weak laws of large numbers in geometric probability

Cited in

(21)

• Limit theorems for random spatial drainage networks
• On a random directed spanning tree
• Explicit laws of large numbers for random nearest-neighbour-type graphs
• The 2D-directed spanning forest is almost surely a tree
• 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
• Laws of large numbers in stochastic geometry with statistical applications
• Linear stochastic equations in the critical case
• 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
• Fixed points of the smoothing transform: two-sided solutions
• A boundary corrected expansion of the moments of nearest neighbor distributions
• Asymptotics of geometrical navigation on a random set of points in the plane
• The smoothing transform: a review of contraction results
• Gaussian approximation for rooted edges in a random minimal directed spanning tree
• 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

Describes a project that uses

Uses Software

• Quicksort

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)