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
Left and right pathlengths in random binary trees
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2006 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 46, no 3-4, 419-429 p.Article in journal (Refereed) Published
Abstract [en]

We study the difference between the left and right total pathlengths in a random binary tree. The results include exact and asymptotic formulas for moments and an asymptotic distribution that can be expressed in terms of either the Brownian snake or ISE. The proofs are based on computing expectations for a subcritical binary Galton-Watson tree, and studying asymptotics as the Galton-Watson process approaches a critical one.

Place, publisher, year, edition, pages
2006. Vol. 46, no 3-4, 419-429 p.
Keyword [en]
random binary tree, total pathlength, left pathlength, right pathlength, Brownian snake, ISE
National Category
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-26314DOI: 10.1007/s00453-006-0099-3ISI: 000243383500009OAI: oai:DiVA.org:uu-26314DiVA: diva2:54088
Note
10th Workshop on the Analysis of Algorithms Berkeley, CA, JUL, 2004 Available from: 2008-01-11 Created: 2008-01-11 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Janson, Svante

Search in DiVA

By author/editor
Janson, Svante
By organisation
Department of Mathematics
In the same journal
Algorithmica
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 357 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