On the Optimality of Some Set Algorithms

DOI10.1145/321724.321730MaRDI QIDQ5659062zbMATH OpenOpenAlexFDO

Authors Edward M. Reingold

Publication date 1972

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/321724.321730

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) General topics in the theory of software (68N01) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Cited in

(15)

• Decision trees: Old and new results.
• Lower bounds on probabilistic linear decision trees
• A time-space tradeoff for sorting on non-oblivious machines
• A lower bound for the edit-distance problem under an arbitrary cost function
• Geometric complexity of some location problems
• A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane
• Checking similarity of planar figures
• On the complexity of inferring functional dependencies
• A probabilistic distributed algorithm for set intersection and its analysis
• On genuinely time bounded computations
• Stable set and multiset operations in optimal time and space
• Finding modes with equality comparisons
• Finding mode using equality comparisons
• A probabilistic lower bound for checking disjointness of sets
• Simulating probabilistic by deterministic algebraic computation trees

This page was built for publication: On the Optimality of Some Set Algorithms

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