Finding Adam in random growing trees

DOI10.1002/rsa.20649zbMath1359.05110arXiv1411.3317OpenAlexW2962848187MaRDI QIDQ2977563

Sébastien Bubeck, Luc P. Devroye, Gábor Lugosi

Publication date: 18 April 2017

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

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

zbMATH Keywords

random treesPólya urnsroot-finding algorithms

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Epicenter of random epidemic spanning trees on finite graphs, Correlated randomly growing graphs, Finding the seed of uniform attachment trees, Root finding algorithms and persistence of Jordan centrality in growing random trees, On a tail bound for analyzing random trees, Influence of the seed in affine preferential attachment trees, Root estimation in Galton–Watson trees, Community modulated recursive trees and population dependent branching processes, Degree centrality and root finding in growing random networks, Fluctuation bounds for continuous time branching processes and evolution of growing trees with a change point, Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms, Change point detection in network models: preferential attachment and long range dependence, Metric dimension of critical Galton-Watson trees and linear preferential attachment trees, Persistence of hubs in growing random networks, Permutation Tests for Infection Graphs, Broadcasting on random recursive trees, The power of adaptivity in source identification with time queries on the path

Cites Work

• Scaling limits and influence of the seed graph in preferential attachment trees
• Limit theorems for triangular urn schemes
• Branching processes in the analysis of the heights of trees
• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• On an elementary proof of some asymptotic formulas in the theory of partitions
• Rumors in a Network: Who's the Culprit?