Publication:4057549
From MaRDI portal
zbMath0302.68010MaRDI QIDQ4057549
Publication date: 1973
Full work available at URL: https://www-cs-faculty.stanford.edu/~knuth/taocp.html
68P10: Searching and sorting
68-02: Research exposition (monographs, survey articles) pertaining to computer science
68N01: General topics in the theory of software
68W99: Algorithms in computer science
Related Items
The algebra of binary search trees, Refined complexity analysis for heap operations, A note on detecting simple redundancies in linear systems, On adaptive sampling, Unification in commutative theories, Improved sorting networks with O(log N) depth, Optimal merging and sorting on the EREW PRAM, Adaptive remeshing for transient problems, A dynamic location problem for graphs, The real zeros of the Bernoulli polynomials, Generating alternating permutations lexicographically, Analysis of recursive batched interpolation search, Tableaux and matrix correspondences, Bijections for refined restricted permutations, On the number of range queries in k-space, Heaps with bits, Proving implications by algebraic approximation, Selection from read-only memory and sorting with minimum data movement, Multiple Quickselect -- Hoare's Find algorithm for several elements, Mellin transforms and asymptotics: Finite differences and Rice's integrals, Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees, On the variance of a class of inductive valuations of data structures for digital search, A parallel tree difference algorithm, Perfectly overlapped merging and sorting on a two-way linear array, Shortest consistent superstrings computable in polynomial time, An algorithm for determining fields of summary multiple waves with source and receiver arbitrarily placed in an elastic medium, Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space, Automaticity. IV: Sequences, sets, and diversity, Improved behaviour of tries by adaptive branching, Is Huffmann coding dead?, Chords, trees and permutations, Animaux et arbres guingois. (Animals and guingois trees), Average-case analysis on simple families of trees using a balanced probability model, Context-free grammars, differential operators and formal power series, On the anti-exceedance distribution on the symmetric group and its subgroups, Sorting twice through a stack, Talus - A quantum Monte Carlo modelling suite, Least-recently-used caching with dependent requests, Faster neighbour list generation using a novel lattice vector representation, Analysis of parallel uniform hashing, How likely is Polya's drunkard to stay in \(x\geq y\geq z\)?, A caution on universal classes of hash functions, A unified algorithm for sorting on multidimensional mesh-connected processors, A generalization of the zero-one principle for sorting algorithms, Parallel algorithms for merging and sorting, How to simulate billiards and similar systems, Analysis of tree algorithms for the simulation event list, Evaluating performance in continuous experiments with feedback to subjects, Computing a longest common subsequence for a set of strings, Upper bounds for sorting integers on random access machines, Asymptotic estimates for the higher moments of the expected behavior of straight insertion sort, A bijection proving orthogonality of the characters of \(S_ n\), The \(r\)-Stirling numbers, Adaptive mesh refinement for hyperbolic partial differential equations, An 0(n log n) algorithm for the convex bipartite matching problem, New trie data structures which support very fast search operations, A simple version of Karzanov's blocking flow algorithm, Minimizing access pointers into trees and arrays, A new parallel sorting algorithm based upon min-mid-max operations, On binary tree encodements, Some average performance measures for the B-tree, A compact hash function for paths in PERT networks, Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings, Hook flag characters and their combinatorics, Multi-version concurrency control scheme for a database system, An analytical comparison of two string searching algorithms, Asymptotic results on the maximal deviation of simple random walks, On search by address computation, The recursive structure of some ordering problems, Efficient sorting during repetitive statistical computations: Algorithms and an application, On parallel integer sorting, Construction of three-dimensional Delaunay triangulations using local transformations, Modular tree transducers, An information and preference theory approach to a discrete resource allocation problem, Parallel comparison algorithms for approximation problems, Hybrid tableaux and the Littlewood-Richardson rule, Catalan numbers and branched coverings by the Riemann sphere, The number of part sizes of a given multiplicity in a random Carlitz composition, Old and young leaves on plane trees, A fast algorithm for computing a longest common increasing subsequence, New permutation coding and equidistribution of set-valued statistics, Knuth relations for the hyperoctahedral groups, On the cost of searching signature trees, A variant of the Ford-Johnson algorithm that is more space efficient, Expressible sharing for functional circuit description, Phase transition in a generalized Eden growth model on a tree, The left-right-imbalance of binary search trees, A complexity O(1) priority queue for event driven molecular dynamics simulations, An improved earliness--tardiness timing algorithm, Quasi-optimal energy-efficient leader election algorithms in radio networks, A data structure useful for finding Hamiltonian cycles, Modeling the dynamics of social systems, Distributing a \(B^+\)-tree in a loosely coupled environment, Exact average message complexity values for distributed election on bidirectional rings of processors, Finding nearest neighbors with Voronoi tessellations, Analysis of the standard deletion algorithms in exact fit domain binary search trees, Performance evaluation of shared and separate inverted files, Slow optimally balanced search strategies vs. cached fast uniformly balanced search strategies, Stable in situ sorting and minimum data movement, Deterministic optimal and expedient move-to-rear list organizing strategies, Binary trees and uniform distribution of traffic cutback, An asymptotically exact polynomial algorithm for equipartition problems, Recurrence relations based on minimization and maximization, More on the complexity of slice functions, Average and worst-case analysis of heuristics for the maximum tardiness problem, On growing a random Young tableau, Rectilinear planar layouts and bipolar orientations of planar graphs, A taxonomy of binary tree traversals, Characterization of partial 3-trees in terms of three structures, The pairing heap: A new form of self-adjusting heap, The complexity of hashing with lazy deletion, Rational equivalence relations, Computing short generator sequences, Random sequential bisection and its associated binary tree, Edge-skeletons in arrangements with applications, Binary search networks: A new method for key searching, Effect of data organization in a system of interleaved memories on the performance of parallel search, Divisor generating functions and insertion into a heap, Polygonizations of point sets in the plane, Automatic evaluation of derivatives, Strong linear independence in bottleneck algebra, Array processing machines: an abstract model, Bijections related to statistics on words, Visibility between two edges of a simple polygon, Halfplanar range search in linear space and \(O(n^{0.695})\) query time, Distributed sorting algorithms for multi-channel broadcast networks, Computing on a free tree via complexity-preserving mappings, On determining the on-line minimax linear fit to a discrete point set in the plane, Information compression and Varshamov-Gilbert bound, Optimal parallel algorithms for constructing and maintaining a balanced m-way search tree, Fractional cascading. II: Applications, A function for evaluating the computing time of a bubbling system, Optimal worst case trees, A \(q\)-Foata proof of the \(q\)-Saalschütz identity, River routing in VLSI, Tridiagonal factorizations of Fourier matrices and applications to parallel computations of discrete Fourier transforms, Stable duplicate-key extraction with optimal time and space bounds, Communication-efficient parallel algorithms for distributed random-access machines, On the use of ordered sets in problems of comparison and consensus of classifications, On-line sorting of twisted sequences in linear time, Modeling splits in file structures, Expected behaviour of \(B^+\)-trees under random insertions, Sorting in constant number of row and column phases on a mesh, Similar constructions for Young tableaux and involutions, and their application to shiftable tableaux, Computing the number of mergings with constraints, Efficient selection on a binary tree, Some average measures in m-ary search trees, A note on the number of leftist trees, A note on the computation on the k-closure of a graph, Polling and greedy servers on a line, On the random construction of heaps, Applications of the theory of records in the study of random trees, Further results on digital search trees, The Euler-Catalan identity, The evaluation of an alternative sum with applications to the analysis of some data structures, Is the data encryption standard a group? (Results of cycling experiments on DES), Concurrency and trie hashing, Distributed algorithms for selection in sets, A computational study of efficient shortest path algorithms, A key distribution system equivalent to factoring, Average complexity of divide-and-conquer algorithms, Fuzzy querying with SQL: Extensions and implementation aspects, Saturated chains of subsets and a random walk, Establishing order in planar subdivisions, On the distribution of comparisons in sorting algorithms, On selecting the k largest with median tests, The computational complexity of asymptotic problems. I: Partial orders, Merging sorted runs using large main memory, Average number of messages for distributed leader-fitting in rings of processors, Scaffold permutations, An \(O(n \log^ 2\,n)\) algorithm for the maximum weighted tardiness problem, A general data structure for image analysis based on a description of connected components, Acyclic directed hypercubes may have exponential diameter, On the balance property of Patricia tries: External path length viewpoint, Weakly adaptive comparison searching, Vandermonde matrices on Chebyshev points, The average diameter of general tree structures, Analytical depoissonization and its applications, Extending STL with efficient data structures, Concurrent manipulation of expanded AVL trees, Lexicographic generation of ordered trees, On the complexity of algorithms for the translation of polynomials, Full table scatter storage parallel searching, Alternating permutations and modified Ghandi-polynomials, Sorting using networks of deques, On a theorem of Chorneyko and Mohanty, Depth-first K-trees and critical path analysis, Optimum multiway search trees, On hash techniques in a paged environment, Data encodings and their costs, Optimal mass production, Ranking arborescences in O(Km log n) time, Determining the mode, Implicit data structures for fast search and update, Binary search trees in secondary memory, Average time behavior of distributive sorting algorithms, Exact formulas for the buddy system, Finding efficient solutions for rectilinear distance location problems efficiently, Open-addressing hashing with unequal-probability keys, Optimal algorithms for sensitivity analysis in associative multiplication problems, Errata to ``Selecting the top three elements by M. Aigner: A result of a computer-assisted proof search, Right invariant metrics and measures of presortedness, Some \(q\)-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths, A direct combinatorial proof of the Jacobi identity, Optimal allocation of priority in a M/M/1 queue with two types of customers, Edge-disjoint spanning trees and depth-first search, On computing the length of longest increasing subsequences, Testing flow graph reducibility, A fast compacting garbage collector, Optimal chain partitions of trees, The analysis of Quicksort programs, On the optimality of algorithms for finite state sequential decision processes, Finding the median, Full table search by polynomial functions, An implementation of hyper-resolution, Reverse plane partitions and tableau hook numbers, Computation sequence sets, Asymptotic miss ratios over independent references, Theil's estimator, An analysis of alpha-beta pruning, A series expansion involving the harmonic numbers, Analysis of a simple factorization algorithm, Non-uniform partial-match file designs, A probabilistic minimum spanning tree algorithm, Synchronization and computing capabilities of linear asynchronous structures, The analysis of double hashing, On random 2-3 trees, Sorting by distributive partitioning, Stirling polynomials, Two rings connected with the inclusion-exclusion principle, Construction of Voronoi polyhedra, One-sided k-height-balanced trees, On the max-entropy rule for a binary search tree, Associative retrieval trie hash-coding, On strings containing all subsets as substrings, A probabilistic proof of a formula for the number of Young tableaux of a given shape, On the correspondence between AVL trees and brother trees, Ricerca random pesata in tavole hash, An algorithmic and complexity analysis of interpolation search, Permutations selon leurs pics, creux, doubles montees et double descentes, nombres d'Euler et nombres de Genocchi, Remarks on A synthesis of several sorting algorithms, Universal classes of hash functions, On The variance of the extremal path length in a symmetric digital trie, Yet another application of a binomial recurrence. Order statistics, Complexity analysis of term-rewriting systems, Strong nondeterministic Turing reduction - a technique for proving intractability, Efficient parallel algorithms for graph problems, On hiding information from an oracle, Implicitly representing arrangements of lines or segments, Heuristics for optimum binary search trees and minimum weight triangulation problems, A bijective census of nonseparable planar maps, Double Horn functions, The distribution of descents in fixed conjugacy classes of the symmetric groups, Unbordered factors of the characteristic sequences of irrational numbers, Dynamic dictionary matching in external memory, A note on hashing functions and tabu search algorithms, The one-dimensional Boltzmann gas: The ergodic hypothesis and the phase portrait of small systems, Fringe thickness and maximum path length of binary trees, Symmetric min-max heap: a simpler data structure for double-ended priority queue, Parallel construction and query of index data structures for pattern matching on square matrices, Multiplicities of eigenvalues of some linear search schemes, Directed animals, forests and permutations, Dyck path enumeration, Enumerative aspects of certain subclasses of perfect graphs, Asymptotic estimation of the average number of terminal states in DAWGs, Descent identities, Hessenberg varieties, and the Weil conjectures, Simulating interpolation search, Analytic variations on quadtrees, Some combinatorial properties of Schubert polynomials, Sorting and computing convex hulls on processor arrays with reconfigurable bus systems, Precision complexity analysis: A case study using insertion sort, A new representation of binary search trees, Computing values of a polynomial with only few multiplications, Queue-mergesort, Optimal dynamic multi-attribute hashing for range queries, On the construction of regular minimal broadcast digraphs, Asymptotic analysis of a class of functional equations and applications, An optimal scheduling algorithm for preemptable real-time tasks, Logical debugging, The analysis of heuristics for search trees, The optimal binary search tree for Andersson's search algorithm, Dynamic programming and graph optimization problems, Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach, Combinatorial statistics on non-crossing partitions, Hybrid reasoning using universal attachment, On competitive on-line algorithms for the dynamic priority-ordering problem, A calculus for the random generation of labelled combinatorial structures, Inverse descents of \(r\)-multipermutations, Two families of Newman lattices, A precise estimation method for locations in an inverse logarithmic potential problem for point mass models, Maximal path length of binary trees, Sorting multisets stably in minimum space, Mellin transforms and asymptotics. The mergesort recurrence, What good are numerical simulations of chaotic dynamical systems?, Algebraic nonlinearity and its applications to cryptography, Hashing lazy numbers, Single machine scheduling with start time dependent processing times: Some solvable cases, Balance in AVL trees and space cost of brother trees, A solution for the \(M^ X/G/1\)-PS process response time, Optimal search trees using two-way key comparisons, Efficient binary space partitions for hidden-surface removal and solid modeling, Task scheduling for parallel sparse Cholesky factorization, Constant time sorting on a processor array with a reconfigurable bus system, The complexity of a simple stochastic OR-tree model in which ``directional search is bad, Parallel general prefix computations with geometric, algebraic, and other applications, Symmetric functions and P-recursiveness, Combinatorial complexity bounds for arrangements of curves and spheres, Worst-case analysis of a generalized heapsort algorithm, A single surface contact algorithm for the post-buckling analysis of shell structures, A locally refined rectangular grid finite element method: Application to computational fluid dynamics and computational physics, Stochastic rearrangement rules for self-organizing data structures, On the height of digital trees and related problems, Weighted dual functions for Bernstein basis satisfying boundary constraints, Improved bounds on sorting by length-weighted reversals, Simultaneous matchings: Hardness and approximation, Weighted height of random trees, Protocol completion incentive problems in cryptographic Vickrey auctions, Trees, functional equations, and combinatorial Hopf algebras, Collision probability for an occupancy problem, Applications of the complexity space to the general probabilistic divide and conquer algorithms, An Ansatz for the asymptotics of hypergeometric multisums, Estimating all possible SUR models with permuted exogenous data matrices derived from a VAR process, Chamfer metrics, the medial axis and mathematical morphology., Should one always use repeated squaring for modular exponentiation?, On the modeling of pedestrian motion, Largest empty circle centered on a query line, Deletions in random binary search trees: a story of errors, The joint distribution of consecutive patterns and descents in permutations avoiding 3-1-2, Growth diagrams for the Schubert multiplication, An efficient counting network, The enumeration of permutations sortable by pop stacks in parallel, Rotation distance is fixed-parameter tractable, Another look at bijections for pattern-avoiding permutations, Designing competitions between teams of individuals, On the learnability of majority rule, Efficient algorithms for finding a longest common increasing subsequence, The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance, Young-Fibonacci insertion, tableauhedron and Kostka numbers, Order statistics and estimating cardinalities of massive data sets, Optimality in external memory hashing, On embedding subclasses of height-balanced trees in hypercubes, Optimal search for rationals, Cuckoo hashing: Further analysis, A new external sorting algorithm with no additional disk space, Parallel merging with restriction, On the uniform convergence of interpolating polynomials, Restricted \(k\)-ary words and functional equations, Bounding restricted rotation distance, Embedding height balanced trees and Fibonacci trees in hypercubes, The bandpass problem: Combinatorial optimization and library of problems, A constant-time dynamic storage allocator for real-time systems, On bijections for pattern-avoiding permutations, A generalization of the 0-1 principle for sorting, \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis, On the average depth of asymmetric LC-tries, Almost avoiding permutations, Transposition of large rectangular matrices, On a problem of Oppenheim concerning Factorisatio Numerorum, Una struttura bidimensionale per la memorizzazione dei file trasposti, The average height of planted plane trees with M leaves, Optimal multiway search trees for variable size keys, Minimal and almost minimal perfect hash function search with application to natural language lexicon design, Approximate counting: a detailed analysis, Purely top-down updating algorithms for stratified search trees, Macro-operators: A weak method for learning, Solution of two sequencing problems, Lower bounds in algebraic computational complexity, Complexity lower bounds for machine computing models, The complexity of finding minimum-length generator sequences, The average height of the second highest leaf of a planted plane tree, A proof of Andrews' \(q\)-Dyson conjecture, A backtracking method for constructing perfect hash functions from a set of mapping functions, An ordered minimal perfect hashing scheme based upon Euler's theorem, Optimal solutions for a class of point retrieval problems, Geometry of a category of complexes and algebraic K-theory, Significant improvements to the Ford-Johnson algorithm for sorting, k-fold bitonic sort on a mesh-connected parallel computer, Possibilistic search trees, A Schensted algorithm for rim hook tableaux, A direct combinatorial proof of a positivity result, A bijective proof of Cassini's Fibonacci identity, Join during merge: an improved sort based algorithm, Binomial determinants, paths, and hook length formulae, Weighted inversion numbers, restricted growth functions, and standard Young tableaux, Database relations with null values, The analysis of simple list structures, General algorithms for the address calculation of lexicographically ordered tuples, Universal retrieval trees, Improved upper bounds on Shellsort, Probabilistic counting algorithms for data base applications, Finding extreme points in three dimensions and solving the post-office problem in the plane, Topological transformations as a tool in the design of systolic networks, Selection of the optimum uniform partition search, New algorithms for the LCS problem, Sequential access in splay trees takes linear time, Low complexity k-dimensional centered forms, Lattice path combinatorics and linear probing, A bijective proof of the q-Saalschütz theorem, Asymptotics of maximal and typical dimensions of irreducible representations of a symmetric group, Interpolation by a sum of exponential functions when some exponents are preassigned, A locally optimized reordering algorithm and its application to a parallel sparse linear system solver, A large index theorem for orthogonal arrays, with bounds, A redundancy eliminating approach to linearly independent rings selection in the ring perception problem, Using two-machine flowshop with maximum lateness objective to model multimedia data objects scheduling problem for WWW applications, Multiprocessor simulation strategies with optimal speed-up, Binary search trees constructed from nondistinct keys with/without specified probabilities, A set expression based inheritance system, Orthogonal queries in segments, On a likely shape of the random Ferrers diagram, On the number of induced subgraphs of trees, Hiding points in arrangements of segments, Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults, When can we sort in \(o(n\log n)\) time?, Varieties of anticommutative \(n\)-ary algebras, Molecular dynamics for polymeric fluids using discontinuous potentials, Catastrophic faults in reconfigurable systolic linear arrays, Fast multiplication of long numbers using FFT, Time-optimal tree computations on sparse meshes, Metrics on permutations useful for positive dependence, Arithmetic progression sums of binomial coefficients, \(\alpha\)-words and factors of characteristic sequences, Concordance between two linear orders: The Spearman and Kendall coefficients revisited, An algebraic approach to the prefix model analysis of binary trie structures and set intersection algorithms, Illumination by floodlights, Perfect hashing, Permutations generated by token passing in graphs, Odd-even sort in powerlists, A representation theorem of the suffixes of characteristic sequences, Efficient simulations of microscopic fluids: algorithm and experiments, Time bounds for selection, A type-B associahedron., Exceedingly deranging!, Architecture independent parallel selection with applications to parallel priority queues, Optimal binary search trees with costs depending on the access paths., Optimizing stable in-place merging., Regular expression simplification, Multicriteria heuristic search., Exact formulas for moments of sums of classical parking functions, Fast searches in a recommendation session., Evaluating different approaches for indexing fuzzy sets., Integrals over Grassmannians and random permutations., Interval-based clock synchronization with optimal precision., The even adjacency split problem for graphs, The heap-mergesort, Computer-supported collaborative argumentation and fuzzy similarity measures in multiple criteria decision making, Cellular telephone networks and random maps in hypergraphs, Presorting algorithms: an average-case point of view, On the variance of the internal path length of generalized digital trees -- the Mellin convolution approach, Periodic comparator networks, Left ternary trees and non-separable rooted planar maps, Legendre-Bernstein basis transformations, On indexed data broadcast, An archiving model for a hierarchical information storage environment, Computing the cycles in the perfect shuffle permutation, Steep polyominoes, \(q\)-Motzkin numbers and \(q\)-Bessel functions, Affine shuffles, shuffles with cuts, the Whitehouse module, and patience sorting, A statistical analysis of an algorithm's complexity, Average-case analysis of algorithms using Kolmogorov complexity, Comparator networks for binary heap construction, Graph-theoretic techniques in D-optimal design problems, Analyzing variants of Shellsort, Randomized splay trees: Theoretical and experimental results., On approximate nearest neighbors under \(l_\infty\) norm, A new class of Wilf-equivalent permutations, An efficient external sorting algorithm, QuickHeapsort, an efficient mix of classical sorting algorithms, Modified binary searching for static tables, Inversion of confluent Vandermonde matrices, Continued fractions and generalized patterns, Random generation of DFAs, Search trees and Stirling numbers, A deterministic skip list for \(k\)-dimensional range search, Mixed Poisson approximation of node depth distributions in random binary search trees, Linear extensions of ranked posets, enumerated by descents. A problem of Stanley from the 1981 Banff conference on ordered sets, An optical model of computation, Gap-free compositions and gap-free samples of geometric random variables, Multiplicity estimating algorithm for zeros of a complex polynomial and its applications, Some Cayley graphs for simple groups, How many random questions are necessary to identify \(n\) distinct objects?, Topologically sweeping visibility complexes via pseudotriangulations, Reaching the bound in the \((2,n)\) merging problem, ``Global graph problems tend to be intractable, New applications of random sampling in computational geometry, Balanced tableaux, An optimal algorithm for search of extrema of a bimodal function, The automated proof of a trace transformation for a bitonic sort, Average sizes of suffix trees and DAWGs, Transforming unbalanced multiway trees into a practical external data structure, Least-cost partition algorithms, Better understanding of Batcher's merging networks, Parallel processing can be harmful: The unusual behavior of interpolation search, Gröbner bases and Stanley decompositions of determinantal ideals, Box-ball systems and Robinson-Schensted-Knuth correspondence, Expected worst-case partial match in random quadtries, On the transformation semigroups of finite automata, Continuous models that are equivalent to randomness for the analysis of many sorting algorithms, Analysis of N-trees, A general class of resource tradeoffs, Parallel sorting, Generalization of Floyd's model of permuting information in idealized two-level storage, Analytical properties of Poincaré series of a loop space, Inserting a new element into a heap, On evaluating strategies for the computation of DWBA integrals, A structure theory for ordered sets, Sorting in one round, Simplification of multiple Fourier series: An example of algorithmic approach, A time-space tradeoff for sorting on non-oblivious machines, A fast algorithm for the longest-common-subsequence problem, The independence of control structures in abstract programming systems, A space-optimal solution of general region location, A generalized counter scheme, Record allocation for minimizing seek delay, Merging of 4 or 5 elements with n elements, The number of increasing subsequences of the random permutation, Multidimensional B-trees: Analysis of dynamic behavior, On the connectivity of a network, The Hillman-Grassl correspondence and the enumeration of reverse plane partitions, Semantics of probabilistic programs, A note on the average depth of trees, Aspects of insertion in random trees, Some modified algorithms for Dijkstra's longest upsequence problem, Tree correspondence problems, Decomposition of group flows in regular matroids, Periodic oscillations of coefficients of power series that satisfy functional equations, Permutation inversions and multidimensional cumulative distribution functions, Simulations among multidimensional Turing machines, Detection of connectivity for regions represented by linear quadtrees, Minimal spanning trees and partial sorting, An O(N log N) planar travelling salesman heuristic based on spacefilling curves, st-ordering the vertices of biconnected graphs, Sorting numbers in linear expected time and optimal extra space, Stratified balanced search trees, An algorithm for finding optimum path in networks, (g//0,g//1,\dots ,g//k)-trees and unary OL systems, Comparisons between linear functions can help, Multichains, non-crossing partitions and trees, Some aspects of groups acting on finite posets, Optimal off-line detection of repetitions in a string, Effects of updates on optimality in tries, The average height of binary trees and other simple trees, How to stay in a set or Koenig's lemma for random paths, Computational algorithms for hierarchically structured project networks, A holonomic systems approach to special functions identities, Voting blocks, reluctant functions, and a formula of Hurwitz, Automatic average-case analysis of algorithms, Higher dimensional restricted lattice paths with diagonal steps, A pointer-free data structure for merging heaps and min-max heaps, Permutation statistics and linear extensions of posets, New modular properties of Bell numbers, Dynamic behaviour in updating process over BST of size two with probabilistic deletion algorithms, Self-adjusting multi-way search trees, Divided \(k-d\) trees, On-line and off-line vertex enumeration by adjacency lists, Stable set and multiset operations in optimal time and space, Randomized optimal algorithm for slope selection, An optimal parallel adaptive sorting algorithm, Parallel Boolean operations for information retrieval, An introduction to randomized algorithms, Closed form expressions for the iterated floor function, Inversion of a recursive tree traversal, Height balance distribution of search trees, Further comments on the subtree isomorphism for ordered trees, Expected time analysis of interpolation merge -- a simple new merging algorithm, A characterization of digital search trees from the successful search viewpoint, A note on multikey sorting using modified binary insertion trees, Randomized incremental construction of Delaunay and Voronoi diagrams, Three priority queue applications revisited, Generating permutations with given ups and downs, Testing the optimality of alphabetic trees, An approximate string-matching algorithm, The complexity of circuit value and network stability, Classical partition functions and the \(U(n+1)\) Rogers-Selberg identity, Computing structure: Sets, structures, and invariants in LISP, Equivalence of the relational algebra and calculus for nested relations, Match algorithms for generalized Rete networks, On the average number of \(k\)-sets, A fixed point theorem for distributions, An affine walk on the hypercube, Distances in random plane-oriented recursive trees, Improved bounds for the expected behaviour of AVL trees, Average search and update costs in skip lists, Quantization of tensor representations and deformation of matrix bialgebras, Gauss's \(_ 2F_ 1(1)\) cannot be generalized to \(_ 2F_ 1(x)\), Arrangement graphs: A class of generalized star graphs, The asymptotic contour process of a binary tree is a Brownian excursion, Polynomial-time compression, FCFS-scheduling in a hard real-time environment under rush-hour conditions, Page usage in a quadtree index, Finding the closest extreme vertex to a fixed point, On the Eulerian numbers \(\displaystyle{ M_ n = \max{}_{1{\leq{}}k{\leq{}}n}A(n,k)}\), An optimal algorithm for generating minimal perfect hash functions, Integral matrices with given row and column sums, Birthday paradox, coupon collectors, caching algorithms and self- organizing search, Some investigations on FCFS scheduling in hard real time applications, Probabilistic modeling of data structures on words. A reply to Professor Andersson's letter, Unbalanced multiway trees improved by partial expansions, Reasoning about qualitative temporal information, Routing and buffer allocation models for a telecommunication system with heterogeneous devices, A heuristic method for generating large random expressions, Mathematical modeling of empirical laws in computer applications: A case study, Updating a balanced search tree in 0(1) rotations, Insertion-safeness in balanced trees, On the control power of integer division, An analogue of the plactic monoid for binary search trees, Restricted rotation distance between binary trees., On computing the diameter of a point set in high dimensional Euclidean space., Some results on tries with adaptive branching., Implementing shared memory on mesh-connected computers and on the fat-tree, Parallel database sorting, On batch-constructing B\(^{+}\)-trees: Algorithm and its performance evaluation, A study of Eulerian numbers by means of an operator on permutations, Divide-and-conquer recurrences associated with generalized heaps, optimal merge, and related structures, A heap-based algorithm for the study of one-dimensional particle systems., Gončarov polynomials and parking functions, Symmetric functions and the Vandermonde matrix, Forbidden subgraphs in connected graphs, Bijections and the Riordan group, Longest increasing subsequences in sliding windows, A framework for adaptive sorting, Parallel tree contraction and prefix computations on a large family of interconnection topologies, A bijective proof of a Touchard-Riordan formula, Enumeration of difference graphs, On Ramanujan's \(Q\)-function, Approximate regular expression pattern matching with concave gap penalties, A new Fortran program for the 9-\(j\) angular momentum coefficient, The order of points on the second convex hull of a simple polygon, Eulerian calculus. III: The ubiquitous Cauchy formula, Bounds on the size of merging networks, Bottom-up mergesort -- A detailed analysis, An estimation method for the number of point masses in an inverse logarithmic potential problem using discrete Fourier transform, Variance of storage requirements for B+-trees, Generating trees and the Catalan and Schröder numbers, Two new bounds on the size of binary codes with a minimum distance of three, A unified \(O(\log N)\) and optimal sorting vector algorithm, Some properties of a limiting distribution in Quicksort, Local search with memory: Benchmarking RTS, Combinatorial representation of invariants of a soliton cellular automaton, Explicit and asymptotic formulae for the expected values of the order statistics of the Cantor distribution, Permutations with forbidden subsequences and nonseparable planar maps, Analytic methods in asymptotic enumeration, Combinatorics of geometrically distributed random variables: Left-to-right maxima, Graphical major indices, Canonical bases and self-evacuating tableaux, Young bitableaux, lattice paths and Hilbert functions, A method for obtaining randomized algorithms with small tail probabilities, Can statistics provide a realistic measure for an algorithm's complexity?, Performance of the move-to-front algorithm with Markov-modulated request sequences, The pivot algorithm: a highly efficient Monte Carlo method for the self-avoiding walk., Geometric properties of random disk packings., Weighted-inversion statistics and their symmetry groups, Optimal disk merge patterns, Optimal in-place transposition of rectangular matrices, A theorem on random polynomials and some consequences in average complexity, An informal analysis of perfect hash function search, Efficient reconstruction of binary trees from their transversals, Mapping dynamic programming onto modular linear systolic arrays, The permutational power of a priority queue, Parallel pointer machines, More analysis of double hashing, Generating linear extensions of posets by transpositions, Balancing sparse Hamiltonian eigenproblems, A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations, Reductions in binary search trees, Tree edge decomposition with an application to minimum ultrametric tree approximation, Learning lexicographic orders, Strategy optimization for deductive games, Smoothed analysis of binary search trees, Efficient and exact quantum compression, Random sorting networks, How robust are average complexity measures? A statistical case study, Probabilistic sorting and stabilization of switched systems, Fast evaluation of the hypergeometric function \(_pF_{p-1}\)(a;b;z) at the singular point \(z = 1\) by means of the Hurwitz zeta function \(\xi(\alpha,s)\)., Renewals for exponentially increasing lifetimes, with an application to digital search trees, A survey on the continuous nonlinear resource allocation problem, The lex game and some applications, Random binary trees: from the average case analysis to the asymptotics of distributions, Technologies of parallel database systems for hierarchical multiprocessor environments, Gaussian processes and neuronal modeling, Longest alternating subsequences of \(k\)-ary words, An architecture independent study of parallel segment trees, Asymptotic distributions for random median quicksort, On monomial graphs of girth eight, On edge-weighted recursive trees and inversions in random permutations, Counting permutations by their alternating runs, Minimization of decision trees is hard to approximate, Complexity and algorithms for nonlinear optimization problems, The class constrained bin packing problem with applications to video-on-demand, Farthest-point queries with geometric and combinatorial constraints, A basis for the non-crossing partition lattice top homology, A proof of Andrews' \(q\)-Dyson conjecture. (Reprint), Guessing probability distributions from small samples, Asymptotic analysis of a leader election algorithm, Online searching with turn cost, Computing interval enclosures for definite integrals by application of triple adaptive strategies, Automatic decomposition of time series into step, ramp, and impulse primitives, A new algorithm for computing orthogonal polynomials, Indexing text with approximate \(q\)-grams, A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times, Optimum extensions of prefix codes., On the arrangement graph., Space and time complexities of balanced sorting on processor arrays, Information, associativity, and choice requirements, On random walks for Pollard's rho method, A fast retrieval technique for large graph structures, An adaptive generic sorting algorithm that uses variable partitioning∗, Relaxed avl trees, main-memory databases and concurrency, Parallel merging on the instruction systolic array, A method for improving full text search using signature files, Implementing heap-object behavior prediction efficiently and effectively, Sorting using heap structure, On the Stack-Size of General Tries, On the number of iterations required by Von Neumann addition, Multiway Trees of Maximum and Minimum Probability under the Random Permutation Model, Discrete optimization methods for multiprocessor computer systems, Runs, Slides and Moments, Hashing techniques, a global approach, On the Horton-Strahler number for random tries, PARALLEL SORT-HASH OBJECT-ORIENTED COLLECTION JOIN ALGORITHMS FOR SHARED-MEMORY MACHINES, Asymptotic analysis of (3, 2, 1)-shell sort, Partial Solution and Entropy, Efficient Construction of Near-Optimal Binary and Multiway Search Trees, Rank-Balanced Trees, Acyclic Preferences and Existence of Sequential Nash Equilibria: A Formal and Constructive Equivalence, Unnamed Item, Expected Costs in Some Classes of Binary Search Trees, On the Most Probable Shape of a Search Tree Grown from a Random Permutation, Parallel distributive partitioned sorting methods, Parallel breadth-first search algorithms for trees and graphs, An optimal time and minimal space algorithm for rectangle intersection problems, An optimal schedule for printing and binding†, Sorting with expensive comparands, Binary search trees with binary comparison cost, Limit laws for local counters in random binary search trees, External VLSI algorithm for the relational database projection operation, A complete characterization of weak inertial coefficient rings, Single-exception sorting networks and the computational complexity of optimal sorting network verification, A sequential sorting network analogous to the batcher merge, Almost Optimal Bounds for Direct Product Threshold Theorem, Hashing with Linear Probing under Nonuniform Probabilities, Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains, Signed words and permutations, I: A fundamental transformation, 𝑞-Eulerian polynomials: Excedance number and major index, Quantum Walk Based Search Algorithms, Deterministic Hot-Potato Permutation Routing on the Mesh and the Torus, POINTERLESS IMPLEMENTATION OF HIERARCHICAL SIMPLICIAL MESHES AND EFFICIENT NEIGHBOR FINDING IN ARBITRARY DIMENSIONS, A Linear In-situ Algorithm for the Power of Cyclic Permutation, A Poisson Approximation for an Occupancy Problem with Collisions, Transitive q-Ary Functions over Finite Fields or Finite Sets: Counts, Properties and Applications, How often are two permutations comparable?, A combinatorial method for calculating the moments of Lévy area, Finding an Unknown Acyclic Orientation of a Given Graph, Performance analysis of index calculus method, Unnamed Item, Unnamed Item, Modelling and simulation of transient noise in circuit simulation, Speeding Up the Pollard Rho Method on Prime Fields, A FAST k-MEANS IMPLEMENTATION USING CORESETS, Hierarchical Adaptive State Space Caching Based on Level Sampling, Reflections on Optimal and Nearly Optimal Binary Search Trees, Maintaining Ideally Distributed Random Search Trees without Extra Space, Difficulties in Forcing Fairness of Polynomial Time Inductive Inference, A Linear Time and Space Algorithm for Detecting Path Intersection, A comparative study of 2-3 trees and AVL trees, Time- and Space-optimal height-balanced 2-3 brother trees, A priority queue in which initialization and queue operations takeO(loglogD) time, Organization of virtual memory in a computer, Explicit Solutions to Optimization Problems on the Intersections of the Unit Ball of the $l_1 $ and $l_\infty $ Norms with a Hyperplane, Asymptotic Normality in the Generalized Polya–Eggenberger Urn Model, with an Application to Computer Data Structures, Hill Climbing with Multiple Local Optima, Tree transformation problem in microparallelism algorithms, External parallel sorting with multiprocessor computers, Formal Techniques for Deriving Binary Search Algorithms, An algorithm for finding shortest paths in a maze, Efficient calculation of hodges-lehmann estimators of location, Amortized Computational Complexity, Unnamed Item, The generalized column incidence graph and a matroid base-listing algorithm, Unnamed Item, Generating subsets of order statistics with applications to trimmed means and means of trimmings, Ranking and Unranking of Non-regular Trees, Solution of a Linear Recurrence Equation Arising in the Analysis of Some Algorithms, Minimization of rounding errors algebraically by use of coding theory, Some Completeness Results on Decision Trees and Group Testing, Merging by the parallel binary search algorithm, On enumerating tree permutations in natural order, A complexity calculus for recursive tree algorithms, Minimum-diameter cyclic arrangements in mapping data-flow graphs onto VLSI arrays, A decidable word problem without equivalent canonical term rewriting system, Extremal properties of ?-weighted binary trees, Optimal organization of multilevel indexed sequential files, Modelling and solving an FMS part selection problem, A limiting distribution for quicksort, On not storing the path of a random walk, Compact storage schemes for formatted files by spanning trees, A method for constructing binary search trees by making insertions at the root, A note on the stack size of regularly distributed binary trees, Self-organizing doubly linked lists†, Analysis of repeated hashing, Sequential vs. random retrieval of a large indexed file, Rotation Distance, Triangulations, and Hyperbolic Geometry, On the distribution of the length of the longest increasing subsequence of random permutations, On the median-of-k version of Hoare's selection algorithm, A note on the generation of binary trees, On random cartesian trees, Note on the heights of random recursive trees and random m‐ary search trees, Balanced ordered trees, Components of Random Forests, Real numbers in factorial representation, A probably fast, provably optimal algorithm for rectilinear Steiner trees, Lower bounds for a subexponential optimization algorithm, Experimental Evaluation of Euler Sums, Generalized fibonacci cubes are mostly hamiltonian, Characteristic Numbers of Permutations, Computing and ranking measures of presortedness, A faster algorithm for sorting on mesh-connected computers with multiple broadcasting using fewer processors, The generalized likelihood ratio test for the pearson correlation∗, Digital search trees with keys of variable length, Nearest-neighbour estimation of semiparametric regression models, Ranking and unrankingk-ary trees with a 4k –4 letter alphabet, Combinatorial Properties of One-Dimensional Arrangements, Stochastic cellular automata, An age-based replacement policy with non-zero repair times for a continuous production process, Combinatorics of rooted trees and Hopf algebras, Random suffix search trees, An almost sure result for path lengths in binary search trees, Enumerating solutions to 𝑝(𝑎)+𝑞(𝑏)=𝑟(𝑐)+𝑠(𝑑), A finite point method for compressible flow, Area efficient layouts of the Batcher sorting networks, Unnamed Item, Unnamed Item, Search for the maximum of a random walk, Scheduling recurrent construction, RANDOMIZED SORTING ON THE POPS NETWORK, A note on the improper use of a formula for Fibonacci numbers, Provably good solutions for the traveling salesman problem, Denert's Permutation Statistic Is Indeed Euler‐Mahonian, Reliability and MTTF prediction ofK-out-of-ncomplex systems with components subjected to multiple stages of degradation, A query-oriented file organization technique, Recent progress in algebraic combinatorics, Unnamed Item, Unnamed Item, Optimal partial-match retrieval, Trees as commutative BCK-Algebras, On a relationship between 2-3 brother trees and dense ternary trees, On the histogram as a density estimator:L 2 theory, The design and implementation of a scheme for large ordered indices, Effective solution of certain problems of theory of schedulings of nets, Stronger players win more knockout tournaments in average, Auxiliary procedures for solving long transportation problems, On Optimal Performance in Self-Organizing Paging Algorithams, On random son-trees, On the design of one-level indexed sequential files, Evaluation of queries based on the extended relational calculi, Minimum dominating cycles in outerplanar graphs, Searching and encoding for infinite ordered sets, Magnetic bubble memory structures for relational database management systems, Query costs in HB(1) trees versus 2?3 trees, A comparison of iterative and defined classes of search trees, The parallel quicksort algorithm part i–run time analysis, Broadcasting in Trees with Multiple Originators, Sorting and Merging in Rounds, An efficient algorithm for K shortest simple paths, Some Monotonicity Properties of Partial Orders, The parallel quicksort algorithm part 2—simulation, The Complexity of Coloring Circular Arcs and Chords, A bijective proof of a factorization theorem for (k,l)-hook schur functions, Functional iteration and the Josephus problem, Divided Differences and Combinatorial Identities, Systolic algorithms for the dynamic programming problem, A note on the probabilistic analysis of patricia trees, An set refinement algorithm with applications, Unnamed Item, Unnamed Item, On some applications of formulae of Ramanujan in the analysis of algorithms, Algorithms On Involutions, A more efficient algorithm for the min-plus multiplication, Transcendental numbers having explicit $g$-adic and Jacobi-Perron expansions, An alternating digital tree (ADT) algorithm for 3D geometric searching and intersection problems, Randomized adaptive sorting, Searching for losers, Hashing the subscripts of a sparse matrix, On the multiplication of poisson series, Storage cost considerations in secondary index selection, Major Index and Inversion Number of Permutations, Analysis of an algorithm for priority queue administration, Multibasic Eulerian Polynomials, On storing ragged arrays by hashing, Partial match retrieval, The efficiency of two indexed priority queue algorithms, Deletion in one-sided height balanced search trees, Simplified odd-even sort using multiple shift-register loops, 2–3 brother trees, Frequency loading and linear probing, Six etudes in generating functions, Universal Limit Laws for Depths in Random Trees, A space efficient algorithm for group structure computation, The Smyth Completion, New classes of interconnection topology structures and their properties, The Largest Degrees of Irreducible Characters of the Symmetric Group, Numeration systems and Markov partitions from self similar tilings, COMPUTING CLOSEST POINTS FOR SEGMENTS, On the distribution of the search cost for the move-to-front rule with random weights, On Tensor-Factorisation Problems,I: The Combinatorial Problem, On evaluating permanents and a matrix of contangents∗, An algorithm for dynamic processing of dawg's, Hypergeometrics and the cost structure of quadtrees, ALGORITHM FOR DATA SAMPLE REPRESENTATION BY HISTOGRAMS WITH UNEQUAL CELL WIDTHS, Analysis of quickselect : an algorithm for order statistics, A generalization of the trie data structure, The move-to-root rule for self-organizing trees with Markov dependent requests∗, Functional Estimation for a Multicomponent Age Replacement Model, A modification of Shanks' baby-step giant-step algorithm, A simplified complexity analysis of mcdiarmid and reed's variant of bottom-up-heapsort, Lagrangean katz family of distributions, Local broadcasting in a tree under minisum criterion, BOUNDING RIGHT-ARM ROTATION DISTANCES, An efficient algorithm for estimating rotation distance between two binary trees, Probabilistic behavior of asymmetric level compressed tries, A Sorting Approach to Indexing Spatial Data, Level of nodes in increasing trees revisited, The empty bin: A data structure for spatial search of time‐varying data, A counting scheme and some algebraic properties of a class of special permutation patterns, Simulating the Bitonic Sort Using P Systems, Crossing Number of Graphs with Rotation Systems, A polynomial algorithm for resourse allocation problems with polymatroid constrains1, A Constructive Method for Building Fuzzy Rule-Based Systems, The height of increasing trees, The Time Value of Ruin in a Sparre Andersen Model, A SURVEY OF FACTORIZATION COUNTING FUNCTIONS, On-line construction of two-dimensional suffix trees, Basket problems in margin calculation: modelling and algorithms., Inhomogeneous sorting, On the combinatorics of leftist trees, The distribution of spacings between small powers of a primitive root, Kazhdan-Lusztig polynomials for 321-hexagon-avoiding permutations, Optimal binary search trees, On a local Lipschitz constant of the maps related to \(LU\)-decomposition, Analysis of two-step index structure for complex spatial objects, Sign-balanced posets, Dynamically maintaining the widest \(k\)-dense corridor, On the average redundancy rate of the Lempel-Ziv code with the \(k\)-error protocol, A limit theorem for “quicksort”, A fast and compact technique of implementing transition tables for finite state automata, Asymptotically efficient in-place merging, Extended convex hull, Rectangular Vandermonde matrices on Chebyshev nodes, Permutations restricted by two distinct patterns of length three, Generalized parking functions, tree inversions, and multicolored graphs, Quasi-parabolic subgroups of \(G(m,1,r)\)., Sorting with fixed-length reversals, Cell-probe lower bounds for the partial match problem, Robust logics, Two-way chaining for non-uniform distributions
