2 citations · 3 across the 5 of their papers we have counts for
5 papers
Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to On-Line Indexing
Amihood Amir, Gianni Franceschini, Roberto Grossi +3
This paper presents a general technique for optimally transforming any dynamic data structure that operates on atomic and indivisible keys by constant-time comparisons, into a data…
Partial Data Compression and Text Indexing via Optimal Suffix Multi-Selection
Gianni Franceschini, Roberto Grossi, S. Muthukrishnan
Consider an input text string T[1,N] drawn from an unbounded alphabet. We study partial computation in suffix-based problems for Data Compression and Text Indexing such as (I) retr…
Optimal cache-aware suffix selection
Gianni Franceschini, Roberto Grossi, S. Muthukrishnan
Given string and integer , the {\em suffix selection} problem is to determine the th lexicographically smallest amongst the suffixes , .…
Radix Sorting With No Extra Space
Gianni Franceschini, S. Muthukrishnan, Mihai Patrascu
It is well known that n integers in the range [1,n^c] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1,U] can be sorted in…
An In-Place Sorting with O(n log n) Comparisons and O(n) Moves
Gianni Franceschini, Viliam Geffert
We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports. This so…