Optimal cache-aware suffix selection (2009)
Franceschini, Gianni, Grossi, Roberto, Muthukrishnan, S.
Given string $S[1..N]$ and integer $k$, the {\em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[i... N]$, $1 \leq i \leq N$. We study the...
Optimal cache-aware suffix selection (2009)
Franceschini, Gianni, Grossi, Roberto, Muthukrishnan, S.
Given string $S[1..N]$ and integer $k$, the {\em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[i\ldots N]$, $1 \leq i \leq N$. We study the...
Optimal cache-aware suffix selection (2009)
Franceschini, Gianni, Grossi, Roberto, Muthukrishnan, S.
Given string $S[1..N]$ and integer $k$, the {\em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[i\ldots N]$, $1 \leq i \leq N$. We study the...
Optimal Cache-Aware Suffix Selection (2009)
Franceschini, Gianni, Grossi, Roberto, Muthukrishnan, S.
Given string $S[1..N]$ and integer $k$, the {em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[ildots N]$, $1 leq i leq N$. We study the suffix...
A General Technique for Managing Strings in Comparison-Driven Data Structures (2008)
Gianni Franceschini, Roberto Grossi
Abstract. This paper presents a general technique for optimally transforming any dynamic data structure D that operates on atomic and indivisible keys by constant-time comparisons, into a data...
Optimal In-Place Sorting of Vectors and Records (2008)
Gianni Franceschini, Roberto Grossi
Abstract. We study the problem of determining the complexity of optimal comparison-based in-place sorting when the key length, k, is not a constant. We present the first algorithm for...
Gianni Franceschini, S. Muthukrishnan
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 can be sorted in O(n √ log log n) time...
Generic Algorithm for 0/1-Sorting (2008)
Gianni Franceschini, Jyrki Katajainen
Abstract. In the 0/1-sorting problem, given a sequence S of elements drawn from a universe E and a characteristic function f: E → {0, 1}, the task is to rearrange the elements in S so that every...
Generic Algorithm for 0/1-Sorting (2008)
Gianni Franceschini, Jyrki Katajainen
Abstract. In the 0/1-sorting problem, given a sequence S of elements drawn from a universe E and a characteristic function f: E → {0, 1}, the task is to rearrange the elements in S so that every...
Gianni Franceschini, Gianni Franceschini
In this paper we give a positive answer to the long-standing problem of finding an in-place sorting algorithm performing O(n log n) comparisons and O(n) data moves in the worst case. So far, the...
Gianni Franceschini, Gianni Franceschini
Let k be a positive integer. A k-cycle is a connected graph in which each vertex has degree greater than k. A k-dense forest is a graph for which no subgraph is a k-cycle; if a k-dense forest is...
Radix Sorting With No Extra Space (2007)
Franceschini, Gianni, Muthukrishnan, S., Patrascu, Mihai
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 O(n sqrt{loglog n})...
Gianni Franceschini, S. Muthukrishnan
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 O(n √ log log...
Radix sorting with no extra space (2007)
Gianni Franceschini, S. Muthukrishnan
Abstract. 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 O(n √...
Gianni Franceschini, Roberto Grossi
Questions about order versus disorder in systems and models have been fascinating scientists over the years. In Computer Science, order is intimately related to sorting, commonly meant as the task of...
Gianni Franceschini, Roberto Grossi
An array of n distinct keys can be sorted for logarithmic searching or can be organized as a heap for logarithmic updating, but it is unclear how to attain logarithmic time for both searching and...
An In-Place Sorting with O(n log n) Comparisons and O(n) Moves (2003)
Franceschini, Gianni, Geffert, Viliam
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 solves a...
Optimal cache-oblivious implicit dictionaries (2003)
Gianni Franceschini, Roberto Grossi
Abstract. We consider the issues of implicitness and cache-obliviousness in the classical dictionary problem for n distinct keys over an unbounded and ordered universe. One finding in this paper is...
Optimal space-time dictionaries over an unbounded universe with flat implicit trees (2003)
Gianni Franceschini, Roberto Grossi
In the classical dictionary problem, a set of n distinct keys over an unbounded and ordered universe is maintained under insertions and deletions of individual keys while supporting search...
Some new results for k-Dense Trees: Graph theory (2001)
Gianni Franceschini, Gianni Franceschini
Let k be a positive integer. A k-cycle is a connected graph in which each vertex has degree greater than k. A k-dense forest is a graph for which no subgraph is a k-cycle; if a k-dense forest is...