uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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
Multivariate normal limit laws for the numbers of fringe subtrees in m-ary search trees and preferential attachment trees
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
Charles Univ Prague, Fac Math & Phys, Dept Appl Math, Malostranske Nam 25, CR-11800 Prague, Czech Republic..
2017 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 24, no 2, P2.51Article in journal (Refereed) Published
Abstract [en]

We study fringe subtrees of random m-ary search trees and of preferential attachment trees, by putting them in the context of generalised Polya urns. In particular we show that for the random m-ary search trees with m <= 26 and for the linear preferential attachment trees, the number of fringe subtrees that are isomorphic to an arbitrary fixed tree T converges to a normal distribution; more generally, we also prove multivariate normal distribution results for random vectors of such numbers for different fringe subtrees. Furthermore, we show that the number of protected nodes in random m-ary search trees for m <= 26 has asymptotically a normal distribution.

Place, publisher, year, edition, pages
ELECTRONIC JOURNAL OF COMBINATORICS , 2017. Vol. 24, no 2, P2.51
Keyword [en]
Random trees, Fringe trees, Normal limit laws, Polya urns, m-ary search trees, Preferential attachment trees, Protected nodes
National Category
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-334501ISI: 000408657300009OAI: oai:DiVA.org:uu-334501DiVA: diva2:1172758
Available from: 2018-01-10 Created: 2018-01-10 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

No full text

Other links

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p51/pdf

Authority records BETA

Holmgren, CeciliaJanson, Svante

Search in DiVA

By author/editor
Holmgren, CeciliaJanson, Svante
By organisation
Department of Mathematics
In the same journal
The Electronic Journal of Combinatorics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 2 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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