2026-04-17T17:37:54Zhttps://recercat.cat/oai/request

oai:recercat.cat:10230/448442025-12-19T23:00:32Zcom_2072_6col_2072_452952

Finding the seed of uniform attachment trees Lugosi, Gábor Pereira, Alan S. Random trees Uniform attachment Discrete probability Seed 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. Gábor Lugosi was supported by the Spanish Ministry of Economy and Competitiveness, Grant MTM2015-67304-P and FEDER, EU. 2020-05-28T08:42:46Z 2020-05-28T08:42:46Z 2019 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Electronic journal of probability. 2019 Jan 22;24(18):1-15 info:eu-repo/grantAgreement/ES/1PE/MTM2015-67304-P Copyright for all articles in EJP is CC BY 4.0. https://creativecommons.org/licenses/by/4.0/ info:eu-repo/semantics/openAccess The Institute of Mathematical Statistics and the Bernoulli Society