Leaf Stripping on Uniform Attachment Trees

Autor:	Addario-Berry, Louigi, Brandenberger, Anna, Briend, Simon, Broutin, Nicolas, Lugosi, Gábor
Rok vydání:	2024
Předmět:	Mathematics - Probability Computer Science - Data Structures and Algorithms Computer Science - Machine Learning Statistics - Machine Learning
Druh dokumentu:	Working Paper
Popis:	In this note we analyze the performance of a simple root-finding algorithm in uniform attachment trees. The leaf-stripping algorithm recursively removes all leaves of the tree for a carefully chosen number of rounds. We show that, with probability $1 - \epsilon$, the set of remaining vertices contains the root and has a size only depending on $\epsilon$ but not on the size of the tree. Comment: 9 pages, 5 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2410.06481 Zobrazit plný text záznamu View this record from Arxiv