774 citations
- University of HelsinkiFI4 papers
- Helsinki Institute of PhysicsFI3 papers
- Austrian Academy of SciencesAT2 papers
- Brera Astronomical ObservatoryIT2 papers
- Goddard Space Flight CenterUS2 papers
- Institute for Quantum Optics and Quantum Information InnsbruckAT2 papers
- Landau Institute for Theoretical PhysicsRU2 papers
- Los Alamos National LaboratoryUS2 papers
- Universität UlmDE2 papers
- University of MichiganUS2 papers
- Adam Mickiewicz University in PoznańPL1 paper
- Agenzia Spaziale ItalianaIT1 paper
5 papers · 1 filter
New Algorithms on Wavelet Trees and Applications to Information Retrieval
Travis Gagie, Gonzalo Navarro, Simon J. Puglisi
Wavelet trees are widely used in the representation of sequences, permutations, text collections, binary relations, discrete points, and other succinct data structures. We show, ho…
Counting Colours in Compressed Strings
Travis Gagie, Juha Kärkkäinen
Suppose we are asked to preprocess a string \(s [1..n]\) such that later, given a substring's endpoints, we can quickly count how many distinct characters it contains. In this pape…
Hardness and Approximation of The Asynchronous Border Minimization Problem
Alexandru Popa, Prudence W. H. Wong, Fencol C. C. Yung
We study a combinatorial problem arising from microarrays synthesis. The synthesis is done by a light-directed chemical process. The objective is to minimize unintended illuminatio…
Lightweight Data Indexing and Compression in External Memory
Paolo Ferragina, Travis Gagie, Giovanni Manzini
In this paper we describe algorithms for computing the BWT and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are light…
Tight Bounds for Online Stable Sorting
Travis Gagie, Yakov Nekrich
Although many authors have considered how many ternary comparisons it takes to sort a multiset of size , the best known upper and lower bounds still differ by a term linear…