Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Fringe trees, Crump-Mode-Jagers branching processes and m-ary search trees
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Probability Theory.
2017 (English)In: Probability Surveys, ISSN 1549-5787, E-ISSN 1549-5787, Vol. 14, p. 53-154Article in journal (Refereed) Published
Abstract [en]

This survey studies asymptotics of random fringe trees and extended fringe trees in random trees that can be constructed as family trees of a Crump-Mode-Jagers branching process, stopped at a suitable time. This includes random recursive trees, preferential attachment trees, fragmentation trees, binary search trees and (more generally) m-ary search trees, as well as some other classes of random trees.

We begin with general results, mainly due to Aldous (1991) and Jagers and Nerman (1984). The general results are applied to fringe trees and extended fringe trees for several particular types of random trees, where the theory is developed in detail. In particular, we consider fringe trees of m-ary search trees in detail; this seems to be new.

Various applications are given, including degree distribution, protected nodes and maximal clades for various types of random trees. Again, we emphasise results for m-ary search trees, and give for example new results on protected nodes in m-ary search trees.

A separate section surveys results on the height of the random trees due to Devroye (1986), Biggins (1995, 1997) and others.

This survey contains well-known basic results together with some additional general results as well as many new examples and applications for various classes of random trees.

Place, publisher, year, edition, pages
2017. Vol. 14, p. 53-154
Keyword [en]
Random trees, fringe Trees, extended fringe trees, m-ary search trees, random recursive trees, preferential attachment trees, fragmentation trees, protected nodes, clades, branching processes
National Category
Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:uu:diva-334109DOI: 10.1214/16-PS272ISI: 000408369200002OAI: oai:DiVA.org:uu-334109DiVA, id: diva2:1160075
Funder
Swedish Research CouncilKnut and Alice Wallenberg Foundation
Available from: 2017-11-24 Created: 2017-11-24 Last updated: 2017-11-29Bibliographically approved

Open Access in DiVA

fulltext(1066 kB)10 downloads
File information
File name FULLTEXT01.pdfFile size 1066 kBChecksum SHA-512
ee7877d1205e6b39fc7805a35bb0ffd05677a60755250643d6378afec0cce116c22d5344b6443cd47922faa9ec3b04617397dde26557ddae307033b24da8f465
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Holmgren, CeciliaJanson, Svante
By organisation
Analysis and Probability Theory
In the same journal
Probability Surveys
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 10 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 87 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf