Tight(er) worst-case bounds on dynamic searching and priority queues

DOI10.1145/335305.335344MaRDI QIDQ3192001zbMATH OpenOpenAlexFDO

Authors Arne Andersson, Mikkel Thorup

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/335305.335344

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Dynamic ordered sets with exponential search trees
• Priority Search Trees
• Publication:4490355
• Binary search trees of almost optimal height
• A unifying property for distribution-sensitive priority queues

Cited in

(19)

• Algorithms and Data Structures
• Dynamic ordered sets with exponential search trees
• Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space
• Dynamic layers of maxima with applications to dominating queries
• On the probabilistic worst-case time of ``find
• Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem
• Compressed data structures: Dictionaries and data-aware measures
• Adjacency queries in dynamic sparse graphs
• Optimal finger search trees in the pointer machine
• Two-dimensional packet classification and filter conflict resolution in the internet
• c-trie++: a dynamic trie tailored for fast prefix searches
• Dynamic interpolation search revisited
• Improved bounds for finger search on a RAM
• Optimal bounds for the predecessor problem and related problems
• On search by address computation
• Rotation and lighting invariant template matching
• Worst case constant time priority queue
• A survey on priority queues
• Orienting dynamic graphs, with applications to maximal matchings and adjacency queries

This page was built for publication: Tight(er) worst-case bounds on dynamic searching and priority queues

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