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

DOI10.1145/335305.335344zbMath1296.68038OpenAlexW2059868876MaRDI QIDQ3192001

Mikkel Thorup, Arne Andersson

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

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

Related Items (14)

Dynamic layers of maxima with applications to dominating queries ⋮ Rotation and lighting invariant template matching ⋮ Adjacency queries in dynamic sparse graphs ⋮ Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries ⋮ c-trie++: a dynamic trie tailored for fast prefix searches ⋮ Improved bounds for finger search on a RAM ⋮ Compressed data structures: Dictionaries and data-aware measures ⋮ Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem ⋮ Two-dimensional packet classification and filter conflict resolution in the internet ⋮ Optimal finger search trees in the pointer machine ⋮ Dynamic interpolation search revisited ⋮ Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space ⋮ A Survey on Priority Queues ⋮ Optimal bounds for the predecessor problem and related problems

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