Search Results

Documents authored by Cicalese, Ferdinando

Document
DOI: 10.4230/LIPIcs.ESA.2026.125
Incongruity-Sensitive Access to Highly Compressed Strings

Authors: Ferdinando Cicalese, Travis Gagie, Zsuzsanna Lipták, Gonzalo Navarro, Nicola Prezza, and Cristian Urbina

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
Random access to highly compressed strings - represented by straight-line programs or Lempel-Ziv parses, for example - is a well-studied topic. Random access to such strings in strongly sublogarithmic time is impossible in the worst case, but previous authors have shown how to support faster access to specific characters and their neighbourhoods. In this paper we explore whether, since better compression can impede access, we can support faster access to less compressible substrings of highly compressed strings. We first show how, given a run-length compressed straight-line program (RLSLP) of size g_{rl} or a block tree of size L, we can build an O (g_{rl})-space or an O (L)-space data structure, respectively, that supports access to any character in time logarithmic in the length of the longest repeated substring containing that character. That is, the more "incongruous" a character is with respect to the characters around, the faster we can support access to it. We then prove a similar but more powerful and sophisticated result for parsings in which phrases' sources do not overlap much larger phrases, with the query time depending also on the number of phrases we must copy from their sources to obtain the queried character.
Cite as

Ferdinando Cicalese, Travis Gagie, Zsuzsanna Lipták, Gonzalo Navarro, Nicola Prezza, and Cristian Urbina. Incongruity-Sensitive Access to Highly Compressed Strings. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 125:1-125:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cicalese_et_al:LIPIcs.ESA.2026.125,
  author =	{Cicalese, Ferdinando and Gagie, Travis and Lipt\'{a}k, Zsuzsanna and Navarro, Gonzalo and Prezza, Nicola and Urbina, Cristian},
  title =	{{Incongruity-Sensitive Access to Highly Compressed Strings}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{125:1--125:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.125},
  URN =		{urn:nbn:de:0030-drops-272611},
  doi =		{10.4230/LIPIcs.ESA.2026.125},
  annote =	{Keywords: Data compression, parsing, straight-line program, random access, grammar compression, run-length grammar, longest repeated substring, distance-sensitive predecessor data structures}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.38
On Constrained Intersection Representations of Graphs and Digraphs

Authors: Ferdinando Cicalese, Clément Dallard, and Martin Milanič

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We study the problem of determining minimal directed intersection representations of DAGs in a model introduced by [Kostochka, Liu, Machado, and Milenkovic, ISIT2019]: vertices are assigned color sets, two vertices are connected by an arc if and only if they share at least one color and the tail vertex has a strictly smaller color set than the head, and the goal is to minimize the total number of colors. We show that the problem is polynomially solvable in the class of triangle-free and Hamiltonian DAGs and also disclose the relationship of this problem with several other models of intersection representations of graphs and digraphs.
Cite as

Ferdinando Cicalese, Clément Dallard, and Martin Milanič. On Constrained Intersection Representations of Graphs and Digraphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cicalese_et_al:LIPIcs.ISAAC.2022.38,
  author =	{Cicalese, Ferdinando and Dallard, Cl\'{e}ment and Milani\v{c}, Martin},
  title =	{{On Constrained Intersection Representations of Graphs and Digraphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.38},
  URN =		{urn:nbn:de:0030-drops-173239},
  doi =		{10.4230/LIPIcs.ISAAC.2022.38},
  annote =	{Keywords: Directed intersection representation, intersection number}
}
Document
DOI: 10.4230/DagSemProc.09281.1
09281 Abstracts Collection – Search Methodologies

Authors: Rudolf Ahlswede, Ferdinando Cicalese, and Ugo Vaccaro

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)

Abstract
From 05.07.09 to 10.07.09, the Dagstuhl Seminar 09281 on ``Search Methodologies '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. Abstracts of the presentations given during the seminar are put together in this paper. The first section describes the seminar topics and goals in general. We also briefly comment on how the topics were addressed in the talks. Links to extended abstracts or full papers are provided, if available.
Cite as

Rudolf Ahlswede, Ferdinando Cicalese, and Ugo Vaccaro. 09281 Abstracts Collection – Search Methodologies. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{ahlswede_et_al:DagSemProc.09281.1,
  author =	{Ahlswede, Rudolf and Cicalese, Ferdinando and Vaccaro, Ugo},
  title =	{{09281 Abstracts Collection – Search Methodologies}},
  booktitle =	{Search Methodologies},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.1},
  URN =		{urn:nbn:de:0030-drops-22457},
  doi =		{10.4230/DagSemProc.09281.1},
  annote =	{Keywords: Search algorithms, group testing, fault-tolerance, identification, decision tree, multi-access communication}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact