Leaf Stripping on Uniform Attachment Trees
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:AZ624IFRrecord.jsonopen to challenge →
classification
math.PR
cs.DScs.LGstat.ML
keywords
algorithmattachmentepsilonsizetreetreesuniformanalyze
read the original 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 - \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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.