A note on predecessor searching in the pointer machine model

DOI10.1016/J.IPL.2009.03.003MaRDI QIDQ989469zbMATH OpenOpenAlexFDO

Authors Wolfgang Mulzer

Publication date 20 August 2010

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

Full work available at URL https://doi.org/10.1016/j.ipl.2009.03.003

zbMATH Keywords

analysis of algorithmsdata structureslower boundpointer machinepredecessor searching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Searching and sorting (68P10)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3081677 (Why is no real title available?)
• A Lower Bound on the Complexity of the Union-Split-Find Problem
• A class of algorithms which require nonlinear time to maintain disjoint sets
• Design and implementation of an efficient priority queue
• Optimal bounds for the predecessor problem and related problems
• Storage Modification Machines
• Time-space trade-offs for predecessor search

Cited in

(3)

• Efficient algorithms for the temporal precedence problem
• scientific article; zbMATH DE number 176163 (Why is no real title available?)
• The temporal precedence problem

This page was built for publication: A note on predecessor searching in the pointer machine model

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