Tight(er) worst-case bounds on dynamic searching and priority queues
From MaRDI portal
Publication:3192001
DOI10.1145/335305.335344zbMath1296.68038MaRDI QIDQ3192001
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
68P10: Searching and sorting
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05: Data structures
Related Items
Optimal finger search trees in the pointer machine, Dynamic layers of maxima with applications to dominating queries, Adjacency queries in dynamic sparse graphs, Optimal bounds for the predecessor problem and related problems, Improved bounds for finger search on a RAM, Two-dimensional packet classification and filter conflict resolution in the internet, Dynamic interpolation search revisited, Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space, Rotation and lighting invariant template matching, 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, c-trie++: a dynamic trie tailored for fast prefix searches, A Survey on Priority Queues, Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries
