Leaf Stripping on Uniform Attachment Trees

Addario-Berry, Louigi; Brandenberger, Anna; Briend, Simon; Broutin, Nicolas; Lugosi, Gábor

doi:10.48550/ARXIV.2410.06481

Back

Preprint

Leaf Stripping on Uniform Attachment Trees

Addario-Berry, Louigi
Brandenberger, Anna
Briend, Simon ORCID UniDistance Suisse
Broutin, Nicolas
Lugosi, Gábor

2024

English 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.

Identifiers

DOI 10.48550/ARXIV.2410.06481
URI https://pub.orcid.org/v3.0/0009-0009-8655-0532/work/183074240
ARK ark:/51647/srd1336044

Persistent URL

https://n2t.net/ark:/51647/srd1336044

Statistics

Document views: 7 File downloads:

Leaf-Stripping-on-Uniform-Attachment-Trees.pdf: 15