Trans-dichotomous algorithms without multiplication — some upper and lower bounds

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

Mathematics Subject Classification ID

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