An algorithm for finding predecessors in integer sets

DOI10.1007/3-540-57155-8_273MaRDI QIDQ5060139zbMATH OpenOpenAlexFDO

Authors Bruce M. Maggs, Monika R. Henzinger

Publication date 18 January 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-57155-8_273

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Data structures (68P05)

Recommendations

• Predecessor queries in dynamic integer sets
• A lower bound for finding predecessors in Yao's cell probe model
• Time-space trade-offs for predecessor search
• Optimal bounds for the predecessor problem
• Optimal bounds for the predecessor problem and related problems

Cites work

• A lower bound for finding predecessors in Yao's cell probe model
• Bounded ordered dictionaries in O(log log N) time and O(n) space
• Hash functions for priority queues
• Preserving order in a forest in less than logarithmic time and linear space
• Should Tables Be Sorted?

Cited in

(9)

• A note on predecessor searching in the pointer machine model
• Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem
• Optimal bounds for the predecessor problem
• A lower bound for finding predecessors in Yao's cell probe model
• Unit-time predecessor queries on massive data sets
• The temporal precedence problem
• Optimal solutions for the temporal precedence problem
• Predecessor queries in dynamic integer sets
• Optimal bounds for the predecessor problem and related problems

This page was built for publication: An algorithm for finding predecessors in integer sets

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