Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2411.18614 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909406597218304 |
|---|---|
| author | Addario-Berry, Louigi Fontaine, Catherine Khanfir, Robin Langevin, Louis-Roy Têtu, Simone |
| author_facet | Addario-Berry, Louigi Fontaine, Catherine Khanfir, Robin Langevin, Louis-Roy Têtu, Simone |
| contents | We consider root-finding algorithms for random rooted trees grown by uniform attachment. Given an unlabeled copy of the tree and a target accuracy $\varepsilon > 0$, such an algorithm outputs a set of nodes that contains the root with probability at least $1 - \varepsilon$. We prove that, for the optimal algorithm, an output set of size $\exp(O(\log^{1/2}(1/\varepsilon)))$ suffices; this bound is sharp and answers a question of Bubeck, Devroye and Lugosi (2017). We prove similar bounds for random regular trees that grow by uniform attachment, strengthening a result of Khim and Loh (2017). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_18614 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal root recovery for uniform attachment trees and $d$-regular growing trees Addario-Berry, Louigi Fontaine, Catherine Khanfir, Robin Langevin, Louis-Roy Têtu, Simone Data Structures and Algorithms Social and Information Networks Probability Statistics Theory 60C05, 05C80, 62M05, 94C15 We consider root-finding algorithms for random rooted trees grown by uniform attachment. Given an unlabeled copy of the tree and a target accuracy $\varepsilon > 0$, such an algorithm outputs a set of nodes that contains the root with probability at least $1 - \varepsilon$. We prove that, for the optimal algorithm, an output set of size $\exp(O(\log^{1/2}(1/\varepsilon)))$ suffices; this bound is sharp and answers a question of Bubeck, Devroye and Lugosi (2017). We prove similar bounds for random regular trees that grow by uniform attachment, strengthening a result of Khim and Loh (2017). |
| title | Optimal root recovery for uniform attachment trees and $d$-regular growing trees |
| topic | Data Structures and Algorithms Social and Information Networks Probability Statistics Theory 60C05, 05C80, 62M05, 94C15 |
| url | https://arxiv.org/abs/2411.18614 |