Nicolas Bousquet

research

∙ 03/19/2023

Metric dimension parameterized by treewidth in chordal graphs

The metric dimension has been introduced independently by Harary, Melter...

0 Nicolas Bousquet, et al. ∙

research

∙ 03/14/2023

A note on the flip distance between non-crossing spanning trees

We consider spanning trees of n points in convex position whose edges ar...

0 Nicolas Bousquet, et al. ∙

research

∙ 01/09/2023

Digraph redicolouring

Given two k-dicolourings of a digraph D, we prove that it is PSPACE-comp...

0 Nicolas Bousquet, et al. ∙

research

∙ 01/06/2023

On the coalitional decomposition of parameters of interest

Understanding the behavior of a black-box model with probabilistic input...

0 Marouane Il Idrissi, et al. ∙

research

∙ 01/05/2023

A note on highly connected K_2,ℓ-minor free graphs

We show that every 3-connected K_2,ℓ-minor free graph with minimum degre...

0 Nicolas Bousquet, et al. ∙

research

∙ 01/05/2023

Extremal Independent Set Reconfiguration

The independent set reconfiguration problem asks whether one can transfo...

0 Nicolas Bousquet, et al. ∙

research

∙ 10/18/2022

The smallest 5-chromatic tournament

A coloring of a digraph is a partition of its vertex set such that each ...

0 Thomas Bellitto, et al. ∙

research

∙ 09/23/2022

Quantile-constrained Wasserstein projections for robust interpretability of numerical and machine learning models

Robustness studies of black-box models is recognized as a necessary task...

0 Marouane Il Idrissi, et al. ∙

research

∙ 05/02/2022

Token sliding on graphs of girth five

In the Token Sliding problem we are given a graph G and two independent ...

0 Valentin Bartier, et al. ∙

research

∙ 04/22/2022

A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems

A graph vertex-subset problem defines which subsets of the vertices of a...

0 Nicolas Bousquet, et al. ∙

research

∙ 04/12/2022

Square coloring planar graphs with automatic discharging

The discharging method is a powerful proof technique, especially for gra...

0 Nicolas Bousquet, et al. ∙

research

∙ 04/12/2022

Galactic Token Sliding

Given a graph G and two independent sets I_s and I_t of size k, the inde...

0 Valentin Bartier, et al. ∙

research

∙ 03/16/2022

Short and local transformations between (Δ+1)-colorings

Recoloring a graph is about finding a sequence of proper colorings of th...

0 Nicolas Bousquet, et al. ∙

research

∙ 02/12/2022

What can be certified compactly?

Local certification consists in assigning labels (called certificates) t...

0 Nicolas Bousquet, et al. ∙

research

∙ 01/12/2022

Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint

We investigate the complexity of finding a transformation from a given s...

0 Nicolas Bousquet, et al. ∙

research

∙ 11/15/2021

Metric dimension on sparse graphs and its applications to zero forcing sets

The metric dimension dim(G) of a graph G is the minimum cardinality of a...

0 Nicolas Bousquet, et al. ∙

research

∙ 10/28/2021

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs

A (unit) disk graph is the intersection graph of closed (unit) disks in ...

0 Marthe Bonamy, et al. ∙

research

∙ 10/05/2021

Local certification of MSO properties for bounded treedepth graphs

The graph model checking problem consists in testing whether an input gr...

0 Nicolas Bousquet, et al. ∙

research

∙ 09/13/2021

Distributed recoloring of interval and chordal graphs

One of the fundamental and most-studied algorithmic problems in distribu...

0 Nicolas Bousquet, et al. ∙

research

∙ 07/30/2021

Local certification of graph decompositions and applications to minor-free classes

Local certification consists in assigning labels to the nodes of a netwo...

0 Nicolas Bousquet, et al. ∙

research

∙ 05/20/2021

(Sub)linear kernels for edge modification problems towards structured graph classes

In a (parameterized) graph edge modification problem, we are given a gra...

0 Gabriel Bathie, et al. ∙

research

∙ 02/21/2021

TS-Reconfiguration of Dominating Sets in circle and circular-arc graphs

We study the dominating set reconfiguration problem with the token slidi...

0 Nicolas Bousquet, et al. ∙

research

∙ 12/21/2020

Recoloring graphs of treewidth 2

Two (proper) colorings of a graph are adjacent if they differ on exactly...

0 Valentin Bartier, et al. ∙

research

∙ 12/04/2020

Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces

The asymptotic dimension is an invariant of metric spaces introduced by ...

0 Marthe Bonamy, et al. ∙

research

∙ 12/03/2020

Distributed algorithms for fractional coloring

In this paper we study fractional coloring from the angle of distributed...

0 Nicolas Bousquet, et al. ∙

research

∙ 07/03/2020

On girth and the parameterized complexity of token sliding and token jumping

In the Token Jumping problem we are given a graph G = (V,E) and two inde...

0 Valentin Bartier, et al. ∙

research

∙ 06/30/2020

Linear transformations between dominating sets in the TAR-model

Given a graph G and an integer k, a token addition and removal (TAR for ...

0 Nicolas Bousquet, et al. ∙

research

∙ 06/25/2020

Reconfiguration of Spanning Trees with Many or Few Leaves

Let G be a graph and T_1,T_2 be two spanning trees of G. We say that T_1...

0 Nicolas Bousquet, et al. ∙

research

∙ 01/13/2020

Packing and covering balls in graphs excluding a minor

We prove that for every integer t> 1 there exists a constant c_t such th...

0 Nicolas Bousquet, et al. ∙

research

∙ 01/06/2020

A note on the simultaneous edge coloring

Let G=(V,E) be a graph. A (proper) k-edge-coloring is a coloring of the ...

0 Nicolas Bousquet, et al. ∙

research

∙ 09/18/2019

When Maximum Stable Set can be solved in FPT time

Maximum Independent Set (MIS for short) is in general graphs the paradig...

0 Édouard Bonnet, et al. ∙

research

∙ 07/03/2019

Linear transformations between colorings in chordal graphs

Let k and d be such that k > d+2. Consider two k-colorings of a d-degene...

0 Nicolas Bousquet, et al. ∙

research

∙ 04/12/2019

The Perfect Matching Reconfiguration Problem

We study the perfect matching reconfiguration problem: Given two perfect...

0 Marthe Bonamy, et al. ∙

research

∙ 03/13/2019

A polynomial version of Cereceda's conjecture

Let k and d be such that k > d+2. Consider two k-colourings of a d-degen...

0 Nicolas Bousquet, et al. ∙

research

∙ 12/13/2018

Shortest Reconfiguration of Matchings

Imagine that unlabelled tokens are placed on the edges of a graph, such ...

0 Nicolas Bousquet, et al. ∙

research

∙ 10/10/2018

Parameterized Complexity of Independent Set in H-Free Graphs

In this paper, we investigate the complexity of Maximum Independent Set ...

0 Édouard Bonnet, et al. ∙

research

∙ 09/14/2018

Reconfiguration of graphs with connectivity constraints

A graph G realizes the degree sequence S if the degrees of its vertices ...

0 Nicolas Bousquet, et al. ∙

research

∙ 06/09/2018

Well-posedness conditions in stochastic inversion problems

Stochastic inversion problems arise when it is wanted to estimate the pr...

0 Mélanie Blazère, et al. ∙

research

∙ 04/27/2018

Detecting and modeling worst-case dependence structures between random inputs of computational reliability models

Uncertain information on input parameters of reliability models is usual...

0 Nazih Benoumechiara, et al. ∙

research

∙ 03/05/2018

EPTAS for Max Clique on Disks and Unit Balls

We propose a polynomial-time algorithm which takes as input a finite set...

0 Marthe Bonamy, et al. ∙

research

∙ 02/15/2018

Distributed coloring in sparse graphs with fewer colors

This paper is concerned with efficiently coloring sparse graphs in the d...

0 Pierre Aboulker, et al. ∙

research

∙ 12/06/2017

An innovative solution for breast cancer textual big data analysis

The digitalization of stored information in hospitals now allows for the...

0 Nicolas Thiebaut, et al. ∙

research

∙ 12/03/2017

Bayesian prior elicitation and selection for extreme values

A major issue of extreme value analysis is the determination of the shap...

0 Nicolas Bousquet, et al. ∙

Nicolas Bousquet

Featured Co-authors