Leaf stripping on uniform attachment trees
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Addario-Berry, Louigi
- dc.contributor.author Brandenberger, Anna
- dc.contributor.author Briend, Simon
- dc.contributor.author Broutin, Nicolas
- dc.contributor.author Lugosi, Gábor
- dc.date.accessioned 2025-11-27T18:41:29Z
- dc.date.available 2025-11-27T18:41:29Z
- dc.date.issued 2025
- dc.date.updated 2025-11-27T18:41:29Z
- dc.description.abstract 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 − 𝜀, the set of remaining vertices contains the root and has a size only depending on 𝜀 but not on the size of the tree.
- dc.format.mimetype application/pdf
- dc.identifier.citation Addario-Berry L, Brandenberger A, Briend S, Broutin N, Lugosi G. Leaf stripping on uniform attachment trees. Random Struct Algorithms. 2025;67(1):e70023. DOI: 10.1002/rsa.70023
- dc.identifier.doi http://dx.doi.org/10.1002/rsa.70023
- dc.identifier.issn 1042-9832
- dc.identifier.uri http://hdl.handle.net/10230/72043
- dc.language.iso eng
- dc.publisher Wiley
- dc.relation.ispartof Random Structures and Algorithms. 2025;67(1):e70023
- dc.rights This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited. © 2025 The Author(s). Random Structures & Algorithms published byWiley Periodicals LLC.
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.rights.uri http://creativecommons.org/licenses/by/4.0/
- dc.subject.keyword Pólya urns
- dc.subject.keyword Random recursive trees
- dc.subject.keyword Random trees
- dc.subject.keyword Root-finding algorithms
- dc.subject.keyword Root reconstruction
- dc.subject.keyword Uniform attachment
- dc.title Leaf stripping on uniform attachment trees
- dc.type info:eu-repo/semantics/article
- dc.type.version info:eu-repo/semantics/publishedVersion