Dorbec, Paul González, Antonio Pennarun, Claire
Power domination in graphs emerged from the problem of monitoring an electrical system by placing as few measurement devices in the system as possible. It corresponds to a variant of domination that includes the possibility of propagation. For measurement devices placed on a set S of vertices of a graph G, the set of monitored vertices is initially...
Defrain, Oscar Nourine, Lhouari
We investigate two different approaches to enumerate minimal dominating sets of a graph using structural properties based on neighborhood inclusion. In the first approach, we define a preference relation on a graph G as a poset on the set of vertices of G. In particular, we consider the poset of closed neighborhood inclusion P(G) and define the not...
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 directed acrylic graph (DAG) compression. A method for quantifying the degree of self-similarity of plants through self-nested trees was introduced by Godin and Ferraro in 2010. The procedure consists of computing a self-nested ...
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...
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 à ...
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 ...
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 ...