Efficient searching using partial ordering

DOI10.1016/0020-0190(81)90005-3zbMath0457.68056OpenAlexW2045807935MaRDI QIDQ1151264

Leonidas J. Guibas, Allan Borodin, Nancy A. Lynch, Andrew Chi-Chih Yao

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90005-3

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items

A tradeoff between search and update time for the implicit dictionary problem ⋮ On the distribution of comparisons in sorting algorithms ⋮ On searching a table consistent with division poset ⋮ Searching rigid data structures ⋮ On the time-space complexity of reachability queries for preprocessed graphs ⋮ A pointer-free data structure for merging heaps and min-max heaps ⋮ The number of tests required to search an unordered table ⋮ Relative complexity of algebras ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ A tradeoff between search and update in dictionaries

Cites Work

• Unnamed Item
• Implicit data structures for fast search and update
• Finding the median
• Time bounds for selection
• A decomposition theorem for partially ordered sets