Efficient searching using partial ordering

DOI10.1016/0020-0190(81)90005-3MaRDI QIDQ1151264zbMATH OpenOpenAlexFDO

Authors Allan Borodin, Leonidas Guibas, Nancy 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)

Cites work

• A decomposition theorem for partially ordered sets
• Finding the median
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Implicit data structures for fast search and update
• Time bounds for selection

Cited in

(10)

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

This page was built for publication: Efficient searching using partial ordering

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