2021/05/11 by Travis Gagie, Gagie, Travis, Sebastian Wild +1
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2105.04965
openalex publication_date 2021/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show how a collection of Euler-tour trees for a forest on n vertices can be stored in 2 n + o (n) bits such that simple queries take constant time, more complex queries take logarithmic time and updates take polylogarithmic amortized time.