Trans-dichotomous algorithms without multiplication — some upper and lower bounds
From MaRDI portal
Publication:5096958
DOI10.1007/3-540-63307-3_80zbMath1497.68553MaRDI QIDQ5096958
J. Ian Munro, Peter Bro Miltersen, Andrej Brodnik
Publication date: 19 August 2022
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-63307-3_80
68W40: Analysis of algorithms
68P10: Searching and sorting
68W05: Nonnumerical algorithms
68P05: Data structures
Related Items
Unnamed Item, Space-Efficient Representations for Glushkov Automata, Arbitrary-size permutation networks using arbitrary-radix switches, Optimal bounds for the predecessor problem and related problems, Rank and select operations on a word, Towards optimal packed string matching, Minimal indices for predecessor search, Dynamic Set Intersection
Cites Work
- Universal classes of hash functions
- Surpassing the information theoretic bound with fusion trees
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- Fast multiplication of large numbers
- Parity, circuits, and the polynomial-time hierarchy
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- A Reliable Randomized Algorithm for the Closest-Pair Problem
- Priority queues: Small, monotone and trans-dichotomous
- Predecessor queries in dynamic integer sets
- Neighbours on a grid
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item