Leaf Stripping on Uniform Attachment Trees

2024/10/09 by Addario-Berry, Louigi, Brandenberger, Anna, Briend, Simon +2
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Probability (math.PR)

paper · doi:10.48550/arxiv.2410.06481

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.

Related

• Optimal root recovery for uniform attachment trees and d-regular growing trees
• Finding the seed of uniform attachment trees
• On the discovery of the seed in uniform attachment trees
• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• Vertices of high degree in the preferential attachment tree