Breakage and restoration in recursive trees

Uniform sequential tree-building aggregation of n particles is analyzed together with the effect of the avalanche that takes place when a subtree rooted at a uniformly chosen vertex is removed. For large n, the expected subtree size is found to be ≃ log n both for the tree of size n and the tree tha...

Descripción completa

Guardado en:
Detalles Bibliográficos
Publicado: 2002
Materias:
Aggregation
Avalanche
Recursive tree
Self-organized criticality
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00219002_v39_n2_p383_Tetzlaff
http://hdl.handle.net/20.500.12110/paper_00219002_v39_n2_p383_Tetzlaff
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_00219002_v39_n2_p383_Tetzlaff
record_format dspace
spelling paper:paper_00219002_v39_n2_p383_Tetzlaff2023-06-08T14:43:03Z Breakage and restoration in recursive trees Aggregation Avalanche Recursive tree Self-organized criticality Uniform sequential tree-building aggregation of n particles is analyzed together with the effect of the avalanche that takes place when a subtree rooted at a uniformly chosen vertex is removed. For large n, the expected subtree size is found to be ≃ log n both for the tree of size n and the tree that remains after an avalanche. Repeated breakage-restoration cycles are seen to give independent avalanches which attain size k (1 ≤ k ≤ n - 1) with probability (k(k + 1))-1 and restored trees that are recursive. 2002 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00219002_v39_n2_p383_Tetzlaff http://hdl.handle.net/20.500.12110/paper_00219002_v39_n2_p383_Tetzlaff
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Aggregation
Avalanche
Recursive tree
Self-organized criticality
spellingShingle Aggregation
Avalanche
Recursive tree
Self-organized criticality
Breakage and restoration in recursive trees
topic_facet Aggregation
Avalanche
Recursive tree
Self-organized criticality
description Uniform sequential tree-building aggregation of n particles is analyzed together with the effect of the avalanche that takes place when a subtree rooted at a uniformly chosen vertex is removed. For large n, the expected subtree size is found to be ≃ log n both for the tree of size n and the tree that remains after an avalanche. Repeated breakage-restoration cycles are seen to give independent avalanches which attain size k (1 ≤ k ≤ n - 1) with probability (k(k + 1))-1 and restored trees that are recursive.
title Breakage and restoration in recursive trees
title_short Breakage and restoration in recursive trees
title_full Breakage and restoration in recursive trees
title_fullStr Breakage and restoration in recursive trees
title_full_unstemmed Breakage and restoration in recursive trees
title_sort breakage and restoration in recursive trees
publishDate 2002
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00219002_v39_n2_p383_Tetzlaff
http://hdl.handle.net/20.500.12110/paper_00219002_v39_n2_p383_Tetzlaff
_version_ 1768544487424917504

Ejemplares similares