Efficient searching using partial ordering

DOI10.1016/0020-0190(81)90005-3zbMATH Open0457.68056OpenAlexW2045807935MaRDI QIDQ1151264FDOQ1151264

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

• Title not available (Why is that?)
• A decomposition theorem for partially ordered sets
• Time bounds for selection
• Finding the median
• Implicit data structures for fast search and update

Cited In (10)

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

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)