Gagnon, Alizée Hassler, Alexander Huang, Jerry Krim-Yee, Aaron Mc Inerney, Fionn Zacarías, Andrés Seamone, Ben Virgile, Virgélot

In the eternal domination game, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices and no more than one guard may occupy a vertex. The goal is to determine the eternal domination number of a graph which is the minimum number of guards re...

Doczkal, Christian Pous, Damien

The labeled multigraphs of treewidth at most two can be described using a simple term language over which isomor-phism of the denoted graphs can be finitely axiomatized. We formally verify soundness and completeness of such an axiomatization using Coq and the mathematical components library. The completeness proof is based on a normalizing and conf...

Tench, C R Tanasescu, Radu Constantinescu, C S Cottam, W J Auer, D P
Published in
NeuroImage

Meta-analysis of summary results from published neuroimaging studies independently testing a common hypothesis is performed using coordinate based meta-analysis (CBMA), which tests for consistent activation (in the case of functional MRI studies) of the same anatomical regions. Using just the reported coordinates it is also possible to meta-analyse...

Cohen, Nathann Mc Inerney, Fionn Nisse, Nicolas Pérennes, Stéphane

In the Spy game played on a graph G, a single spy travels the vertices of G at speed s, while multiple slow guards strive to have, at all times, one of them within distance d of that spy. In order to determine the smallest number of guards necessary for this task, we analyze the game through a Linear Programming formulation and the fractional strat...

Santana Maia, Deise

The wide literature on graph theory invites numerous problems to be modeled in the framework of graphs. In particular, clustering and segmentation algorithms designed this framework can be applied to solve problems in various domains, including image processing, which is the main field of application investigated in this thesis. In this work, we fo...

Bonifati, Angela Holubovà, Irena Prat-Pérez, Arnau

We focus on the computational complexity of regular simple path queries (RSPQs). We consider the following problem RSPQ(L) for a regular language L: given an edge-labeled digraph Gand two nodes xand y, is there a simple path from x to y that forms a word belonging to L? We fully characterize the frontier between tractability and intractability for ...

Bagan, Guillaume Bonifati, Angela Groz, Benoit

We focus on the computational complexity of regular simple path queries (RSPQs). We consider the following problem RSPQ(L) for a regular language L: given an edge-labeled digraph Gand two nodes xand y, is there a simple path from x to y that forms a word belonging to L? We fully characterize the frontier between tractability and intractability for ...

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...

Bansal, N. (Nikhil) Svensson, O. (Ola) Trevisan, L. (Luca)

A sparsifier of a graph G (Benczúr and Karger; Spielman and Teng) is a sparse weighted subgraph G that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs in which different edges have different weights. Even for graphs that admit

Renton, Guillaume Héroux, Pierre Adam, Sébastien Gaüzère, Benoit

In this paper, we propose a new method to simultaneously detect and classify symbols in floorplan images. This method relies on the very recent developments of Graph Neural Networks (GNN). In the proposed approach, floorplan images are first converted into Region Adjacency Graphs (RAGs). Within those graphs, each node corresponds to a white region ...