Numerical studies of the asymptotic height distribution in binary search trees.
On parameters of an evaluation function for heuristic search as a path problem
On the median-of- version of Hoare’s selection algorithm
On the median-of-k version of Hoare's selection algorithm
In Hoare's (1961) original version of the algorithm the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question. Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergence in distribution of the number of comparisons required and obtain a simple explicit result for the limiting average performance of the median-of-three version.
On the number of descendants and ascendants in random search trees.
On the stack-size of general tries
Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural assumptions...
On the Stack-Size of General Tries
Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural...
Ontologies and soft computing in flexible querying
Parallel computation on 2-3-trees
Parallel probabilistic searching and sorting algorithms
Partially persistent search trees with transcript operations.
Perfect simulation from the quicksort limit distribution.
Periodic sorting using minimum delay, recursively constructed merging networks.
Quasi-Optimal Range Searching in Spaces of Finite VC-Dimension.
Quicksort algorithm again revisited.
Random subnetworks of random sorting networks.
Reversal distance for strings with duplicates: linear time approximation using hitting set.
Search trees and bubble memories
Seriation with applications in philology
Space-efficient parallel merging