Fusion trees can be implemented with \(AC^0\) instructions only

DOI10.1016/S0304-3975(98)00172-8zbMath0915.68121OpenAlexW2018338704WikidataQ56454625 ScholiaQ56454625MaRDI QIDQ1287094

Mikkel Thorup, Peter Bro Miltersen, Arne Andersson

Publication date: 29 April 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00172-8

zbMATH Keywords

fusion tree

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (12)

Dynamic range majority data structures ⋮ Worst-Case Optimal Adaptive Prefix Coding ⋮ A fast algorithm for adaptive prefix coding ⋮ On the succinct representation of equivalence classes ⋮ A correction to Andersson's fusion tree construction ⋮ Approximate pattern matching with \(k\)-mismatches in packed text ⋮ The saga of minimum spanning trees ⋮ Subquadratic algorithms for 3SUM ⋮ Minimal indices for predecessor search ⋮ Space-efficient Huffman codes revisited ⋮ Finding median in read-only memory on integer input ⋮ Optimal bounds for the predecessor problem and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Surpassing the information theoretic bound with fusion trees
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• Organization and maintenance of large ordered indexes
• Hash functions for priority queues

This page was built for publication: Fusion trees can be implemented with \(AC^0\) instructions only