A survey of multivariate aspects of the contraction method

MaRDI QIDQ5387665zbMATH OpenFDO

Authors Ralph Neininger, Ludger Rüschendorf

Publication date 27 May 2008

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/issue/view/82/showToc.html

zbMATH Keywords

analysis of algorithmsbranching processesbranching recurrencesrandom trees

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Central limit and other weak theorems (60F05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• The contraction method for recursive algorithms
• On a multivariate contraction method for random recursive structures with applications to quicksort
• scientific article; zbMATH DE number 2247656
• scientific article; zbMATH DE number 1392847
• On the contraction method with degenerate limit equation.

Cited in

(19)

• A general limit theorem for recursive algorithms and combinatorial structures
• The contraction method for recursive algorithms
• On the contraction method with degenerate limit equation.
• Exact formulas for the variance of several balance indices under the Yule model
• Heavy tailed solutions of multivariate smoothing transforms
• The fixed points of the multivariate smoothing transform
• On a multivariate contraction method for random recursive structures with applications to quicksort
• The growth of iterates of multivariate generating functions
• A general central limit theorem for shape parameters of m-ary tries and PATRICIA tries
• Balanced multicolour Pólya urns via smoothing systems analysis
• Dependence between path-length and size in random digital trees
• scientific article; zbMATH DE number 939772 (Why is no real title available?)
• scientific article; zbMATH DE number 2247656 (Why is no real title available?)
• On 2-protected nodes in random digital trees
• Support, absolute continuity and harmonic moments of fixed points of the multivariate smoothing transform
• Smoothing equations for large Pólya urns
• Weighted height of random trees
• On the silhouette of binary search trees
• The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance

This page was built for publication: A survey of multivariate aspects of the contraction method

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