228 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Sapienza University of RomeIT12 papers
- Santa Fe InstituteUS7 papers
- University of PalermoIT5 papers
- University of PisaIT5 papers
- Adolfo Ibáñez UniversityCL4 papers
- Central European UniversityAT4 papers
- Scuola Normale SuperioreIT4 papers
- University of MacerataIT4 papers
- University of OxfordGB4 papers
- Centre National de la Recherche ScientifiqueFR3 papers
- ERABLE: Equipe de recherche européenne en algorithmique et biologie formelle et expérimentaleFR3 papers
- Massachusetts Institute of TechnologyUS3 papers
6 papers · 1 filter
Planar Reachability Under Single Vertex or Edge Failures
Giuseppe F. Italiano, Adam Karczmarz, Nikos Parotsidis
In this paper we present an efficient reachability oracle under single-edge or single-vertex failures for planar directed graphs. Specifically, we show that a planar digraph ca…
Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták +3
The Burrows-Wheeler-Transform (BWT), a reversible string transformation, is one of the fundamental components of many current data structures in string processing. It is central in…
All-Pairs LCA in DAGs: Breaking through the barrier
Fabrizio Grandoni, Giuseppe F. Italiano, Aleksander Łukasiewicz +2
Let be an -vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices and is a common ancestor of and such that no descend…
Dominating Sets and Connected Dominating Sets in Dynamic Graphs
Niklas Hjuler, Giuseppe F. Italiano, Nikos Parotsidis +1
In this paper we study the dynamic versions of two basic graph problems: Minimum Dominating Set and its variant Minimum Connected Dominating Set. For those two problems, we present…
Optimal Substring-Equality Queries with Applications to Sparse Text Indexing
Nicola Prezza
We consider the problem of encoding a string of length from an integer alphabet of size so that access and substring equality queries (that is, determining the equality of…
Decompressing Lempel-Ziv Compressed Text
Philip Bille, Mikko Berggren Ettienne, Travis Gagie +2
We consider the problem of decompressing the Lempel--Ziv 77 representation of a string of length using a working space as close as possible to the size of the input. Th…