Tight(er) worst-case bounds on dynamic searching and priority queues
DOI10.1145/335305.335344zbMATH Open1296.68038OpenAlexW2059868876MaRDI QIDQ3192001FDOQ3192001
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
Recommendations
Data structures (68P05) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (19)
- 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
- A Survey on Priority Queues
- Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency 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
- Optimal finger search trees in the pointer machine
- Adjacency queries in dynamic sparse graphs
- 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
- Algorithms and Data Structures
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)
