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 (17)

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?

This page was built for publication: Finding Adam in random growing trees