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

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

Cited in

(17)

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

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)