Leaf Stripping on Uniform Attachment Trees
<|reference_start|>Leaf Stripping on Uniform Attachment Trees: 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.<|reference_end|>
@article{addario-berry2024leaf,
    title={Leaf Stripping on Uniform Attachment Trees},
    author={Louigi Addario-Berry, Anna Brandenberger, Simon Briend, Nicolas
  Broutin, G'abor Lugosi},
    journal={arXiv preprint arXiv:2410.06481},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.06481},
    primaryClass={math.PR cs.DS cs.LG stat.ML}
}