Optimal root recovery for uniform attachment trees and $d$-regular growing trees

Louigi Addario-Berry, Catherine Fontaine, Robin Khanfir +2

We consider root-finding algorithms for random rooted trees grown by uniform attachment. Given an unlabeled copy of the tree and a target accuracy $\epsilon >0$, such an algori…