Finding the seed of uniform attachment trees
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Lugosi, Gábor
- dc.contributor.author Pereira, Alan S.
- dc.date.accessioned 2020-05-28T08:42:46Z
- dc.date.available 2020-05-28T08:42:46Z
- dc.date.issued 2019
- dc.description.abstract A uniform attachment tree is a random tree that is generated dynamically. Starting from a fixed “seed” tree, vertices are added sequentially by attaching each vertex to an existing vertex chosen uniformly at random. Upon observing a large (unlabeled) tree, one wishes to find the initial seed. We investigate to what extent seed trees can be recovered, at least partially. We consider three types of seeds: a path, a star, and a random uniform attachment tree. We propose and analyze seed-finding algorithms for all three types of seed trees.en
- dc.description.sponsorship Gábor Lugosi was supported by the Spanish Ministry of Economy and Competitiveness, Grant MTM2015-67304-P and FEDER, EU.
- dc.format.mimetype application/pdf
- dc.identifier.citation Lugosi G, Pereira AS. Finding the seed of uniform attachment trees. Electron J Probab. 2019 Jan 22;24(18):1-15. DOI: 10.1214/19-EJP268
- dc.identifier.doi http://dx.doi.org/10.1214/19-EJP268
- dc.identifier.issn 1083-6489
- dc.identifier.uri http://hdl.handle.net/10230/44844
- dc.language.iso eng
- dc.publisher The Institute of Mathematical Statistics and the Bernoulli Society
- dc.relation.ispartof Electronic journal of probability. 2019 Jan 22;24(18):1-15
- dc.relation.projectID info:eu-repo/grantAgreement/ES/1PE/MTM2015-67304-P
- dc.rights Copyright for all articles in EJP is CC BY 4.0.
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.rights.uri https://creativecommons.org/licenses/by/4.0/
- dc.subject.keyword Random treesen
- dc.subject.keyword Uniform attachmenten
- dc.subject.keyword Discrete probabilityen
- dc.subject.keyword Seeden
- dc.title Finding the seed of uniform attachment treesen
- dc.type info:eu-repo/semantics/article
- dc.type.version info:eu-repo/semantics/publishedVersion