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

DOI10.1007/3-540-63307-3_80zbMath1497.68553OpenAlexW1493544477MaRDI 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

Analysis of algorithms (68W40) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Data structures (68P05)

Related Items (8)

Dynamic Set Intersection ⋮ Arbitrary-size permutation networks using arbitrary-radix switches ⋮ Unnamed Item ⋮ Towards optimal packed string matching ⋮ Space-Efficient Representations for Glushkov Automata ⋮ Rank and select operations on a word ⋮ Minimal indices for predecessor search ⋮ Optimal bounds for the predecessor problem and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Trans-dichotomous algorithms without multiplication — some upper and lower bounds