| dc.contributor.author | Addario‐Berry, Louigi | |
| dc.contributor.author | Brandenberger, Anna | |
| dc.contributor.author | Briend, Simon | |
| dc.contributor.author | Broutin, Nicolas | |
| dc.contributor.author | Lugosi, Gábor | |
| dc.date.accessioned | 2025-10-29T16:54:01Z | |
| dc.date.available | 2025-10-29T16:54:01Z | |
| dc.date.issued | 2025-08-04 | |
| dc.identifier.issn | 1042-9832 | |
| dc.identifier.issn | 1098-2418 | |
| dc.identifier.uri | https://hdl.handle.net/1721.1/163405 | |
| dc.description.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 noton the size of the tree. | en_US |
| dc.publisher | Wiley | en_US |
| dc.relation.isversionof | https://doi.org/10.1002/rsa.70023 | en_US |
| dc.rights | Creative Commons Attribution | en_US |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | en_US |
| dc.source | Wiley | en_US |
| dc.title | Leaf Stripping on Uniform Attachment Trees | en_US |
| dc.type | Article | en_US |
| dc.identifier.citation | Addario-Berry, L., Brandenberger, A., Briend, S., Broutin, N. and Lugosi, G. (2025), Leaf Stripping on Uniform Attachment Trees. Random Struct Alg, 67: e70023. | en_US |
| dc.contributor.department | Massachusetts Institute of Technology. Department of Mathematics | en_US |
| dc.relation.journal | Random Structures & Algorithms | en_US |
| dc.eprint.version | Final published version | en_US |
| dc.type.uri | http://purl.org/eprint/type/JournalArticle | en_US |
| eprint.status | http://purl.org/eprint/status/PeerReviewed | en_US |
| dc.identifier.doi | https://doi.org/10.1002/rsa.70023 | |
| dspace.date.submission | 2025-10-29T16:45:46Z | |
| mit.journal.volume | 67 | en_US |
| mit.journal.issue | 1 | en_US |
| mit.license | PUBLISHER_CC | |
| mit.metadata.status | Authority Work and Publication Information Needed | en_US |
