3 papers
cs.DS2026
Achieving Optimal Redundancy for Small Dynamic Rank/Select Dictionaries
Gabriel Marques Domingues
In this paper, we study the number of bits required to construct a dynamic dictionary with optimal time for operations. Using the standard (multipli…
cs.DS2026
Dynamic Edge Orientation via Random Walks: From Trees to Outerplanar Graphs and Beyond
Gabriel Marques Domingues, Minh Hang Nguyen, Shay Solomon
We study the \emph{fully dynamic edge orientation problem}, focusing on \emph{worst-case} time bounds. An undirected graph undergoes edge insertions and deletions, and the goal is…
cs.DS2026
Compressing Dynamic Fully Indexable Dictionaries in Word-RAM
Gabriel Marques Domingues
We study the problem of constructing a dynamic fully indexable dictionary (FID) in the Word-RAM model using space close to the information-theoretic lower bound. A FID is a data-st…