Showing 2024Show all
3 papers · 1 filter
math.PR2024
Leaf Stripping on Uniform Attachment Trees
Louigi Addario-Berry, Anna Brandenberger, Simon Briend +2
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…
math.PR2024
Random friend trees
Louigi Addario Berry, Simon Briend, Luc Devroye +3
We study a random recursive tree model featuring complete redirection called the random friend tree and introduced by Saramäki and Kaski. Vertices are attached in a sequential mann…
stat.ML2024
Estimating the history of a random recursive tree
Simon Briend, Christophe Giraud, Gábor Lugosi +1
This paper studies the problem of estimating the order of arrival of the vertices in a random recursive tree. Specifically, we study two fundamental models: the uniform attachment…