research
∙
03/19/2023
Metric dimension parameterized by treewidth in chordal graphs
The metric dimension has been introduced independently by Harary, Melter...
share
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...
research
∙
01/09/2023
Digraph redicolouring
Given two k-dicolourings of a digraph D, we prove that it is PSPACE-comp...
research
∙
01/06/2023
On the coalitional decomposition of parameters of interest
Understanding the behavior of a black-box model with probabilistic input...
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...
research
∙
01/05/2023
Extremal Independent Set Reconfiguration
The independent set reconfiguration problem asks whether one can transfo...
research
∙
10/18/2022
The smallest 5-chromatic tournament
A coloring of a digraph is a partition of its vertex set such that each ...
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...
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 ...
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...
research
∙
04/12/2022
Square coloring planar graphs with automatic discharging
The discharging method is a powerful proof technique, especially for gra...
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...
research
∙
03/16/2022
Short and local transformations between (Δ+1)-colorings
Recoloring a graph is about finding a sequence of proper colorings of th...
research
∙
02/12/2022
What can be certified compactly?
Local certification consists in assigning labels (called certificates) t...
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...
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...
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 ...
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...
research
∙
09/13/2021
Distributed recoloring of interval and chordal graphs
One of the fundamental and most-studied algorithmic problems in distribu...
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...
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...
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...
research
∙
12/21/2020
Recoloring graphs of treewidth 2
Two (proper) colorings of a graph are adjacent if they differ on exactly...
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 ...
research
∙
12/03/2020
Distributed algorithms for fractional coloring
In this paper we study fractional coloring from the angle of distributed...
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...
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 ...
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...
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...
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 ...
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...
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...
research
∙
04/12/2019
The Perfect Matching Reconfiguration Problem
We study the perfect matching reconfiguration problem: Given two perfect...
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...
research
∙
12/13/2018
Shortest Reconfiguration of Matchings
Imagine that unlabelled tokens are placed on the edges of a graph, such ...
research
∙
10/10/2018
Parameterized Complexity of Independent Set in H-Free Graphs
In this paper, we investigate the complexity of Maximum Independent Set ...
research
∙
09/14/2018
Reconfiguration of graphs with connectivity constraints
A graph G realizes the degree sequence S if the degrees of its vertices ...
research
∙
06/09/2018
Well-posedness conditions in stochastic inversion problems
Stochastic inversion problems arise when it is wanted to estimate the pr...
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...
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...
research
∙
02/15/2018
Distributed coloring in sparse graphs with fewer colors
This paper is concerned with efficiently coloring sparse graphs in the d...
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...
research
∙
12/03/2017