The contraction method for recursive algorithms
From MaRDI portal
Publication:1840499
zbMath0967.68166MaRDI QIDQ1840499
Ludger Rüschendorf, Uwe Roesler
Publication date: 11 February 2001
Published in: Algorithmica (Search for Journal in Brave)
Related Items (66)
Distribution of distances in random binary search trees. ⋮ Limit laws for partial match queries in quadtrees ⋮ One-sided variations on binary search trees ⋮ Implicit Renewal Theory and Power Tails on Trees ⋮ On the contraction method with degenerate limit equation. ⋮ The Weighted Branching Process ⋮ Distances in random digital search trees ⋮ Parameterised branching processes: a functional version of Kesten \& Stigum theorem ⋮ Recursive partition structures ⋮ Limit laws for two distance-based indices in random recursive tree models ⋮ On the size of paged recursive trees ⋮ Note on the exponential recursive k-ary trees ⋮ Smoothing equations for large Pólya urns ⋮ Towards rigorous analysis of the Levitov–Mirlin–Evers recursion ⋮ DEGREE PROFILE OF HIERARCHICAL LATTICE NETWORKS ⋮ Central limit theorem in uniform metrics for generalized Kac equations ⋮ Almost sure convergence to the quicksort process ⋮ Tail behavior of solutions of linear recursions on trees ⋮ A recursive distributional equation for the stable tree ⋮ The quicksort process ⋮ Distributional convergence for the number of symbol comparisons used by QuickSort ⋮ Implicit renewal theorem for trees with general weights ⋮ Exact and approximate limit behaviour of the Yule tree's cophenetic index ⋮ Process convergence for the complexity of radix selection on Markov sources ⋮ The analysis of range quickselect and related problems ⋮ Maximums on trees ⋮ Limit distributions for multitype branching processes of \(m\)-ary search trees ⋮ On the number of jumps of random walks with a barrier ⋮ A general limit theorem for recursive algorithms and combinatorial structures ⋮ Weighted height of random trees ⋮ Complexity Questions in Non-Uniform Random Variate Generation ⋮ Random binary trees: from the average case analysis to the asymptotics of distributions ⋮ On the number of segregating sites for populations with large family sizes ⋮ On the Variety of Shapes on the Fringe of a Random Recursive Tree ⋮ Asymptotic distributions for random median quicksort ⋮ The size of random fragmentation trees ⋮ Convergence Rates in the Implicit Renewal Theorem on Trees ⋮ Asymptotic Properties of a Leader Election Algorithm ⋮ Cost functionals for large (uniform and simply generated) random trees ⋮ Revisiting Shao and Sokal's \(B_2\) index of phylogenetic balance ⋮ Perpetuities in Fair Leader Election Algorithms ⋮ The functional equation of the smoothing transform ⋮ Endogeny for the logistic recursive distributional equation ⋮ Singularity analysis, Hadamard products, and tree recurrences ⋮ A survey of max-type recursive distributional equations ⋮ On the silhouette of binary search trees ⋮ On stochastic recursive equations of sum and max type ⋮ A limit field for orthogonal range searches in two-dimensional random point search trees ⋮ Asymptotic joint normality of counts of uncorrelated motifs in recursive trees ⋮ Information ranking and power laws on trees ⋮ All solutions of the stochastic fixed point equation of the Quicksort process ⋮ Symmetric fixed points of a smoothing transformation ⋮ Limit laws for the Randić index of random binary tree models ⋮ Inversions in Split Trees and Conditional Galton–Watson Trees ⋮ On the total length of the random minimal directed spanning tree ⋮ Stochastic fixed-point equations ⋮ Convergence of the population dynamics algorithm in the Wasserstein metric ⋮ Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect ⋮ Limit distribution of distances in biased random tries ⋮ Fixed points with finite variance of a smoothing transformation. ⋮ On weighted branching processes in random environment. ⋮ The Smoothing Transform: A Review of Contraction Results ⋮ On a functional contraction method ⋮ Selection by rank inK-dimensional binary search trees ⋮ Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm ⋮ On binary search tree recursions with monomials as toll functions
This page was built for publication: The contraction method for recursive algorithms
