375 citations · 440 across the 15 of their papers we have counts for
16 papers · 1 filter
Weighted Ancestors in Suffix Trees Revisited
Djamal Belazzougui, Dmitry Kosolobov, Simon J. Puglisi +1
The weighted ancestor problem is a well-known generalization of the predecessor problem to trees. It is known to require time for queries provided $O(n\mathop{\math…
Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták +2
A prefix normal word is a binary word with the property that no substring has more s than the prefix of the same length. By proving that the set of prefix normal words is a bubb…
m-Bonsai: a Practical Compact Dynamic Trie
Andreas Poyias, Simon J. Puglisi, Rajeev Raman
We consider the problem of implementing a space-efficient dynamic trie, with an emphasis on good practical performance. For a trie with nodes with an alphabet of size , the…
Tree Compression with Top Trees Revisited
Lorenz Hübschle-Schneider, Rajeev Raman
We revisit tree compression with top trees (Bille et al, ICALP'13) and present several improvements to the compressor and its analysis. By significantly reducing the amount of info…
On Succinct Representations of Binary Trees
Pooya Davoodi, Rajeev Raman, Srinivasa Rao Satti
We observe that a standard transformation between \emph{ordinal} trees (arbitrary rooted trees with ordered children) and binary trees leads to interesting succinct binary tree rep…
Encoding Range Minimum Queries
Pooya Davoodi, Gonzalo Navarro, Rajeev Raman +1
We consider the problem of encoding range minimum queries (RMQs): given an array A[1..n] of distinct totally ordered values, to pre-process A and create a data structure that can a…