On the shape of the fringe of various types of random trees

DOI10.1002/MMA.1085zbMATH Open1181.68334OpenAlexW1988381024MaRDI QIDQ3634637FDOQ3634637

Authors: Michael Drmota, Bernhard Gittenberger, Alois Panholzer, Helmut Prodinger, Mark Daniel Ward 

Publication date: 25 June 2009

Published in: Mathematical Methods in the Applied Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/mma.1085

Recommendations

• On the variety of shapes on the fringe of a random recursive tree
• On the Contour of Random Trees
• On the profile of random trees
• Asymptotic fringe distributions for general families of random trees
• Distinct fringe subtrees in random trees
• Pattern distribution in various types of random trees

zbMATH Keywords

analysis of algorithmspattern matchingsimply generated treessuffix treesbinary search treesdigital search treesrecursive treestriesPatricia trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms (68W40) Data structures (68P05)

Cites Work

• Singularity Analysis of Generating Functions
• Mellin transforms and asymptotics: Harmonic sums
• Two Notes on Notation
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Mathematics for the Analysis of Algorithms.
• Two Probability Models of Pyramid or Chain Letter Schemes Demonstrating that Their Promotional Claims are Unreliable
• Limit laws for local counters in random binary search trees
• Digital Search Trees Revisited
• On the Altitude of Nodes in Random Trees
• String overlaps, pattern matching, and nontransitive games
• File structures using hashing functions
• Analytical depoissonization and its applications
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Title not available (Why is that?)
• Analysis of the average depth in a suffix tree under a Markov model
• Periods in strings
• Total Path Length for Random Recursive Trees
• On pattern frequency occurrences in a Markovian sequence
• Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach
• On the number of terminal vertices in certain random trees with an application to stemma construction in philology
• Asymptotic distributions and a multivariate Darboux method in enumeration problems
• The height distribution of leaves in rooted trees
• Error Resilient LZ'77 Data Compression: Algorithms, Analysis, and Experiments
• Title not available (Why is that?)

Cited In (4)

• Asymptotic fringe distributions for general families of random trees
• An analytic approach to the asymptotic variance of trie statistics and related structures
• Fringe analysis of plane trees related to cutting and pruning
• Limit theorems for patterns in phylogenetic trees

This page was built for publication: On the shape of the fringe of various types of random trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3634637)