853 citations
- Sorbonne UniversitéFR398 papers
- Centre National de la Recherche ScientifiqueFR380 papers
- Université Paris CitéFR136 papers
- Université Pierre-et-Marie-CurieFR97 papers
- University of EdinburghGB89 papers
- Institut national de recherche en sciences et technologies du numériqueFR85 papers
- Université Paris-SaclayFR67 papers
- University of OxfordGB54 papers
- École PolytechniqueFR50 papers
- Sorbonne Paris CitéFR48 papers
- Massachusetts Institute of TechnologyUS45 papers
- Universidade Federal do Rio de JaneiroBR45 papers
5 papers · 2 filters
Lower bounds for text indexing with mismatches and differences
Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya
In this paper we study lower bounds for the fundamental problem of text indexing with mismatches and differences. In this problem we are given a long string of length , the "tex…
An Information-theoretic Framework for the Lossy Compression of Link Streams
Robin Lamarche-Perrin
Graph compression is a data analysis technique that consists in the replacement of parts of a graph by more general structural patterns in order to reduce its description length. I…
Scheduling under dynamic speed-scaling for minimizing weighted completion time and energy consumption
Christoph Dürr, Łukasz Jeż, Oscar C. Vásquez
Since a few years there is an increasing interest in minimizing the energy consumption of computing systems. However in a shared computing system, users want to optimize their expe…
Parameterized Power Vertex Cover
Eric Angel, Evripidis Bampis, Bruno Escoffier +1
We study a recently introduced generalization of the Vertex Cover (VC) problem, called Power Vertex Cover (PVC). In this problem, each edge of the input graph is supplied with a po…
Online Maximum Matching with Recourse
Spyros Angelopoulos, Christoph Dürr, Shendan Jin
We study the online maximum matching problem in a model in which the edges are associated with a known recourse parameter . An online algorithm for this problem has to maintain…