Finding the root in random nearest neighbor trees

DOI10.1002/RSA.70057MaRDI QIDQ7227400zbMATH OpenFDO

Authors Elchanan Mossel, Madhu Sudan

Publication date 10 April 2026

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/RSA.70057

zbMATH Keywords

growing random geometric graphnetwork archaeologyrandom nearest neighbor treeroot finding algorithms

Mathematics Subject Classification ID

Combinatorics (05-XX) Computer science (68-XX)

Cites work

• A Geometric Preferential Attachment Model of Networks
• A spatial preferential attachment model with local clustering
• Archaeology of random recursive dags and Cooper-Frieze random networks
• Asymptotic theory for the multidimensional random on-line nearest-neighbour graph
• Cost of sequential connection for points in space
• Degree centrality and root finding in growing random networks
• Estimating the history of a random recursive tree
• Eve, Adam and the preferential attachment tree
• Explicit laws of large numbers for random nearest-neighbour-type graphs
• Finding Adam in random growing trees
• Inference on the History of a Randomly Growing Tree
• Limit theory for the random on‐line nearest‐neighbor graph
• Multivariate spatial central limit theorems with applications to percolation and spatial graphs
• New results for the random nearest neighbor tree
• On the measure of Voronoi cells
• Phase transitions for random geometric preferential attachment graphs
• Quantitative CLTs on the Poisson space via Skorohod estimates and p-Poincaré inequalities
• Random partitions of the plane via Poissonian coloring and a self-similar process of coalescing planar partitions
• Root estimation in Galton–Watson trees
• Root finding algorithms and persistence of Jordan centrality in growing random trees

This page was built for publication: Finding the root in random nearest neighbor trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7227400)