Tremblay, Nicolas Barthelmé, Simon Amblard, Pierre-Olivier

When one is faced with a dataset too large to be used all at once, an obvious solution is to retain only part of it. In practice this takes a wide variety of different forms, but among them " coresets " are especially appealing. A coreset is a (small) weighted sample of the original data that comes with a guarantee: that a cost function can be eval...

Cazaux, Bastien Lecroq, Thierry Rivals, Eric

DNA sequencing technologies have tremendously increased their throughput, and hence complicated DNA assembly. Numerous assembly programs use de Bruijn graphs (dBG) built from short reads to merge these into contigs, which represent putative DNA segments. In a dBG of order k, nodes are substrings of length k of reads (or k-mers), while arcs are thei...

Azaïs, Romain

Self-nested trees present a systematic form of redundancy in their subtrees and thus achieve optimal compression rates by DAG compression. A method for quantifying the degree of self-similarity of plants through self-nested trees has been introduced by Godin and Ferraro in 2010. The procedure consists in computing a self-nested approximation, calle...

Gupta, Siddharth Kosowski, Adrian Viennot, Laurent

For fixed $h \geq 2$, we consider the task of adding to a graph $G$ a set of weighted shortcut edges on the same vertex set, such that the length of a shortest $h$-hop path between any pair of vertices in the augmented graph is exactly the same as the original distance between these vertices in $G$. A set of shortcut edges with this property is cal...

Giannopoulou, Archontia C. Pilipczuk, Michał Raymond, Jean-Florent Thilikos, Dimitrios M. Wrochna, Marcin
Published in
Algorithmica

Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that...

Berenbrink, Petra Klasing, Ralf Kosowski, Adrian Mallmann-Trenn, Frederik Uznanski, Przemyslaw

We consider the problem of deterministic load balancing of tokens in the discrete model. A set of $n$ processors is connected into a $d$-regular undirected network. In every time step, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the mo...

Casamayou, Alexandre Cohen, Nathann Connan, Guillaume Dumont, Thierry Fousse, Laurent Maltey, Francois Meulien, Matthias Mezzarobba, Marc Pernet, Clement Thiery, Nicolas M.
...

International audience

Bouzat, Nicolas

Les architectures de calcul haute performance les plus récentes intègrent deplus en plus de n\oe uds de calcul qui intègrent eux-mêmes plus de c\oe urs. Lesbus mémoires et les réseaux de communication sont soumis à un niveaud'utilisation critique. La programmation parallèle sur ces nouvelles machinesnécessite de porter une attention particulière à ...

Radanne, Gabriel Thiemann, Peter

Regular expressions are part of every programmer's toolbox. They are used for a wide variety of language-related tasks and there are many algorithms for manipulating them. In particular, matching algorithms that detect whether a word belong to the language described by a regular expression is both a well explored area, yet one that still receives f...

Mercier, Quentin

Cette thèse s’intéresse à l’optimisation multiobjectif sans contrainte lorsque les objectifs sont exprimés comme des espérances de fonctions aléatoires. L’aléa est modélisé par l’intermédiaire de variables aléatoires et on considère qu’il n’impacte pas les variables d’optimisation du problème. La thèse consiste à proposer un algorithme de descente ...