|
Nicolas Bousquet
|
|
nicolas DOT bousquet AT cnrs DOT fr
Phone: +334 56 57 48 19
|
CNRS Researcher, LIRIS, Lyon, France.
|
Bureau H327
Laboratoire LIRIS
Univ. Claude Bernard Lyon 1
Bâtiment Nautibus
43, Bd. du 11 novembre 1918
69622 Villeurbanne Cedex - France
|
Since October 2016, I am a CNRS researcher. I am currently working in Lyon in the LIRIS laborarory in the team GOAL (Graphs algOrithms and AppLications). Previously I was in Grenoble in the G-SCOP laboratory where I was a member of the Combinatorial Optimization (OC) team.
We are currently organizing a virtual seminar until things go back to normal. There is one seminar every two weeks usually. For more information, you can go to the GRAA (Graphes en Rhone Alpes Auvergne) webpage. Most of the talks are recorded. If you want to see more talks, you can for instance enjoy the Frontiers of Parameterized Complexity registered presentations, as well as KAIST Discrete Mathematics seminars or Matroid union seminars. I order to see live seminars (about discrete mathematics and graph theory or algorithms), many of the announcements are centralized here or there.
Formerly, I was an ATER (temporary assistant professor position) in Ecole Centrale de Lyon during the academic year 2015-2016. I was a member of the LIRIS laboratory in the GOAL (Graphes, AlgOrithmes et AppLications) team. Before, I was a postodoctoral fellow at the Department of Mathematics and Statistics at McGill University where I worked with Adrian Vetta. My scholarship was partially funded by the GERAD (Groupe d'études et de recherche en analyse des décisions) at Université de Montréal.
I have defended my PhD the 9-th of December 2013 under the direction of Stéphane Bessy and Stéphan Thomassé at the Université Montpellier 2 (LIRMM). Its title was "Hitting sets, VC-dimension and Multicut". The manuscript can be found there and the slides of the defense can be found there.
I am interested in graph theory, game theory and combinatorics.
My topics of research include but are not limited to:
- Graph reconfigurations problems, especially reconfiguration of colorings and independent sets.
- Structural graph theory and all its applications including graph coloring.
- Parameterized algorithms and polynomial kernels.
- Economic game theory including spectrum auctions and payoff distributions.
I am the french PI of the ANR project GrR (Graph Reconfiguration).
I was the frech PI of the PHC franco-japanese "Sakura" project DATCORE (Development of Algorithmic Techniques for COmbinatorial REconfiguration). In 2019, I co-organized (with Marthe Bonamy), the third edition of the CoRe (Combinatorial Reconfiguration) workshop in Aussois (see here for more information).
Here is a list of current and former PhD students:
- 2020-.... Quentin Deschamps, LIRIS, Université Lyon 1 (with Hamamache Kheddouci and Aline Parreau).
- 2018-2021 Valentin Bartier, G-SCOP, Grenoble-INP (with Myriam Preissmann).
- 2017-2020. Alice Joffard, LIRIS, Université Lyon 1 (with Hamamache Kheddouci).
- 2016-2019. Marc Heinrich, LIRIS, Université Lyon 1 (with Eric Duchêne and Sylvain Gravier). Marc is now post-doc at Leeds University.
In order to access to the paper, click on the icon. To access to the slides of the presentations, click on the icon. When already available online, you can access to the paper on the editor webpage via the icon .
International journals
- Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces, with Marthe Bonamy, Louis Esperet, Carla Groenland, Chun-Hung Liu, François Pirot, Alex Scott.
To appear in Journal of the European Mathematical Society (2023).
- Token Sliding on graphs of girth five, with
Valentin Bartier, Jihad Hanna, Amer E. Mouawad, Sebastian Siebertz.
To appear in Algorithmica.
- The smallest 5-chromatic tournament, with Thomas Bellitto, Adam Kabela and Théo Pierron.
To appear in AMS Mathematics of Computation.
- A note on the flip distance between non-crossing spanning trees, with Valentin Gledel, Jonathan Narboni, Théo Pierron.
To appear in Computation in Geometry and Topology.
- Feedback Vertex Set Reconfiguration in Planar Graphs, with Felix Hommelsheim, Yusuke Kobayashi, Moritz Muehlenthaler and Akira Suzuki.
To appear in Theoretical Computer Science.
- Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint, with Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki and Kunihiro Wasa.
To appear in Algorithmica.
- Galactic Token Sliding, with Valentin Bartier and Amer Mouawad.
Journal of Compututers and System Systems, volume 136, pp. 220-248 (2023).
- Extremal Independent Set Reconfiguration, with Bastien Durain, Théo Pierron and Stéphan Thomassé.
Electronic Journal on Combinatorics Volume 30(3) (2023).
- Improved square coloring of planar graphs, with Quentin Deschamps, Lucas de Meyer, Théo Pierron.
Discrete Mathematics, volume 346(4): 113288 (2023).
- Recolouring planar graphs of girth at least five, with Valentin Bartier, Carl Feghali, Marc Heinrich, Benjamin Moore and Théo Pierron.
SIAM Journal on Discrete Mathematics, volume 37(1), pp. 332-350 (2023).
- Locating-dominating sets: from graphs to oriented graphs, with Quentin Deschamps, Tuomo Lehtilä and Aline Parreau.
Discrete Mathematics, Volume 346(1) (2023).
- A polynomial version of Cereceda's conjecture, with Marc Heinrich.
Journal on Combinatorial Theory, Ser. B, volume 155, pp. 1-16 (2022).
- Degeneracy of Pt-free and Ct-free graphs with no large complete bipartite subgraphs, with Marthe Bonamy, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé, Bartosz Walczak.
Journal on Combinatorial Theory, Series B, volume 152, pp. 353-378 (2022).
- Chordal directed graphs are not chi-bounded, with Pierre Aboulker and Rémi de Joannis de Verclos.
Electronic Journal on Combinatorics, volume 29(2) (2022).
- EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs, with Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, Florian Sikora and Stéphan Thomassé.
Journal of the ACM, volume 68(2), pp. 1-38 (2021).
- Frozen (Delta+1)-colourings of bounded degree graphs, with Marthe Bonamy and Guillem Perarnau.
Combinatorics, Probability and Computing, volume 30(3), pp. 330-343 (2021).
- Graph Isomorphism for (H1,H2)-Free Graphs: An Almost Complete Dichotomy, with Marthe Bonamy, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma, Théo Pierron.
Algorithmica, volume 83(3), pp. 822-852 (2021).
- On girth and the parameterized complexity of token sliding and token jumping, with Valentin Bartier, Clement Dallard, Kyle Lomer and Amer Mouawad.
Algorithmica, volume 83(9), pp. 2914-2951 (2021).
- Recoloring graphs of treewidth 2, with Valentin Bartier and Marc Heinrich.
Discrete Mathematics, volume 344(12): 112553 (2021).
- Packing and covering balls in graphs excluding a minor, with Wouter Cames van Batenburg, Louis Esperet, Gwenaël Joret, William Lochet, Carole Muller, François Pirot.
Combinatorica, volume 41(3), pp. 299-318 (2021).
- Parameterized Complexity of Independent Set in H-Free Graphs with Édouard Bonnet, Pierre Charbit, Stéphan Thomassé and Rémi Watrigant.
Algorithmica 82(8), pp. 2360-2394 (2020).
- A note on the simultaneous edge-coloring, with Bastien Durain.
Discrete Mathematics, 343(5): 111781 (2020).
- A proof of the Erdos-Sands-Sauer-Woodrow conjecture, with William Lochet and Stéphan Thomassé.
Journal on Combinatorial Theory, Ser. B, vol.137 (2019), pp. 316-319.
- Exact distance coloring in trees, with Louis Esperet, Ararat Harutyunyan and Rémi de Joannis de Verclos.
Combinatorics, Probability and Computing, vol. 28(2) (2019), pp. 177-186.
- On a conjecture of Mohar concerning Kempe equivalence, with Marthe Bonamy, Carl Feghali and Matthew Johnson.
Journal on Combinatorial Theory, Series B, vol. 135 (2019) pp. 179-199.
- Multicut is FPT, with Jean Daligault and Stéphan Thomassé.
SIAM Journal on Computing, vol. 47(1) (2018) pp. 166-207.
- Recoloring graphs via tree-decompositions, with Marthe Bonamy.
European Journal on Combinatorics, vol. 69 (2018) pp. 200-213.
- Chi-bounded families of oriented graphs, with Pierre Aboulker, Jorgen Bang-Jensen, Pierre Charbit, Frédéric Havet, Frédéric Maffray and José Zamora.
Journal on Graph Theory, vol. 89(3) (2018) pp. 304-326.
- Decomposition techniques applied to the Clique-Stable set Separation problem, with Aurélie Lagoutte, Frédéric Maffray and Lucas Pastor.
Discrete Mathematics, vol. 341(5) (2018), pp. 1492-1501.
-
A Vizing-like theorem for union vertex-distinguishing edge coloring, with Antoine Dailly, Eric Duchêne, Hamamache Kheddouci et Aline Parreau.
Discrete Applied Mathematics, vol. 232 (2017), pp. 88-98.
-
Colourful paths for 3-chromatic graphs, with Stéphane Bessy.
Discrete Mathematics vol. 340(5) (2017) pp. 1000-1007.
-
Fast recoloring of sparse graphs, with Guillem Perarnau.
European Journal of Combinatorics, vol. 52 (2016), pp. 1-11.
-
The Erdos-Hajnal Conjecture for long holes and antiholes, with Marthe Bonamy and Stéphan Thomassé.
SIAM Journal on Discrete Mathematics, vol. 30(2) (2015), pp 1159-1164.
-
Identifying codes in hereditary classes of graphs and VC-dimension, with Aurélie Lagoutte, Zhentao Li, Aline Parreau and Stéphan Thomassé.
SIAM Journal on Discrete Mathematics, vol. 29-4 (2015), pp. 2047-2064.
-
VC-dimension and Erdös-Pósa property, with Stéphan Thomassé.
Discrete Mathematics, vol. 338-12 (2015) pp. 2302-2317.
-
The Erdos-Hajnal Conjecture for Paths and Antipaths, with Aurélie Lagoutte and Stéphan Thomassé.
Journal of Comb. Theory Series B, vol. 113 (2015), pp. 261-264.
-
Excluding cycles with a fixed number of chords, with Pierre Aboulker.
Discrete Applied Mathematics vol. 180 (2015) 11-24.
[Bibtex ][Bibtex ]
@article{AboulkerBousquet2015,
title = "Excluding cycles with a fixed number of chords ",
author = "P. Aboulker and N. Bousquet",
journal = "Discrete Applied Mathematics ",
volume = "180",
number = "0",
pages = "11 - 24",
year = "2015",
doi = "http://dx.doi.org/10.1016/j.dam.2014.08.006"
}
-
Clique versus independent set, with Aurélie Lagoutte and Stéphan Thomassé.
European Journal of Combinatorics 40 (2014), 73-92.
[Bibtex ][Bibtex ]
@article{BLT14,
author = {N. Bousquet and
A. Lagoutte and
S. Thomass{\'e}},
title = {Clique versus independent set},
journal = {Eur. J. Comb.},
volume = {40},
year = {2014},
pages = {73-92},
ee = {http://dx.doi.org/10.1016/j.ejc.2014.02.003},
}
-
Brooks' theorem on powers of graphs, with Marthe Bonamy.
Discrete Mathematics vol. 325 (2014), 12-16.
[Bibtex ][Bibtex ]
@ARTICLE{BB14,
author = {M. Bonamy and
N. Bousquet},
title = {Brooks' theorem on powers of graphs },
journal = {Discrete Mathematics },
year = {2014},
volume = {325},
pages = {12 - 16},
doi = {http://dx.doi.org/10.1016/j.disc.2014.01.024},
issn = {0012-365X},
}
-
Parameterized Domination in Circle Graphs, with Daniel Gonçalves, George Mertzios, Christophe Paul, Ignasi Sau and Stéphan Thomassé.
Theory of Computing Systems vol. 54(1):45-72, 2014.
[Bibtex ][Bibtex ]
@article{BGMPST14,
author = {N. Bousquet and
D. Gon\c{c}alves and
G. B. Mertzios and
C. Paul and
I. Sau and
S. Thomass{\'e}},
title = {Parameterized Domination in Circle Graphs},
journal = {Theory Comput. Syst.},
volume = {54},
number = {1},
year = {2014},
pages = {45-72},
}
-
Scott's induced subdivision conjecture for maximal triangle-free graphs, with Stéphan Thomassé.
Combinatorics, Probability and Computing, vol. 21 (2012) 512-514.
[Bibtex ][Bibtex ]
@article{BT12,
author = {N. Bousquet and
S. Thomass{\'e}},
title = {Scott's Induced Subdivision Conjecture for Maximal Triangle-Free Graphs},
journal = {Combinatorics, Probability {\&} Computing},
volume = {21},
number = {4},
year = {2012},
pages = {512-514},
ee = {http://dx.doi.org/10.1017/S0963548312000065},
}
International Conferences
- Metric dimension parameterized by treewidth in chordal graphs, with Quentin Deschamps and Aline Parreau.
To appear in WG'23.
- What can be certified compactly?, with Laurent Feuilloley and Théo Pierron.
To appear in PODC'22.
- Galactic Token Sliding, with Valentin Bartier and Amer Mouawad.
To appear in ESA'22.
- Token Sliding on graphs of girth give, with
Valentin Bartier, Jihad Hanna, Amer E. Mouawad, Sebastian Siebertz.
To appear in WG'22.
- Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint, with Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki and Kunihiro Wasa.
STACS'22, pp. 15:1-15:21.
- Local certification of graph decompositions and applications to minor-free classes, with Laurent Feuilloley and Théo Pierron.
Brief announcement in DISC'21, pp. 49:1-49:4.
OPODIS'21, pp. 22:1-22:17.
- Distributed recoloring of interval and chordal graphs, with Laurent Feuilloley, Marc Heinrich and Mikaël Rabie.
OPODIS'21, pp. 19:1-19:17.
- PACE Solver Description: PaSTEC - PAths, Stars and Twins to Edit Towards Clusters, with Valentin Bartier, Gabriel Bathie, Marc Heinrich, Théo Pierron, Ulysse Prieto.
IPEC 2021, pp. 29:1-29:4.
- PACE Solver Description: μSolver - Heuristic Track, with Valentin Bartier, Gabriel Bathie, Marc Heinrich, Théo Pierron, Ulysse Prieto.
IPEC 2021, pp. 33:1-33:3.
- (Sub)linear kernels for edge modification problems towards structured graph classes, with Gabriel Bathie and Théo Pierron.
IPEC'21, pp. 8:1-8:14.
- TS-Reconfiguration of Dominating Sets in circle and circular-arc graphs, with Alice Joffard.
FCT'21, pp. 114-134.
- Distributed algorithms for fractional coloring, with Louis Esperet and François Pirot.
SIROCCO'21, pp. 15-30.
- On girth and the parameterized complexity of token sliding and token jumping, with Valentin Bartier, Clement Dallard, Kyle Lomer and Amer Mouawad.
ISAAC'20, pp. 44:1-44:17.
- Linear transformations between dominating sets in the TAR-model, with Alice Joffard, Paul Ouvrard.
ISAAC'20, pp. 37:1-37:14.
- Reconfiguration of Spanning Trees with Many or Few Leaves, with Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki and Kunihiro Wasa,
ESA'20, pp. 24:1-24:15.
- Approximating Sorting by reversals for trees, with Alice Joffard.
SOFSEM'20, pp. 76-87.
- Linear transformations between colorings in chordal graphs, with Valentin Bartier.
ESA'19, pp. 24:1-24:15.
- When Maximum Stable Set can be solved in FPT time, with Edouard Bonnet, Stéphan Thomassé and Rémi Watrigant.
ISAAC'19, pp. 49:1-49:22.
- The Perfect Matching Reconfiguration Problem, with Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kabayahi, Arnaud Mary, Moritz Mühlenthaler and Kunihiro Wasa.
MFCS'19, pp. 80:1-80:14.
- The distance between Matchings, with Tatsuhiko Hatanaka, Takehiro Ito and Moritz Mühlenthaler.
WG'19, pp. 162-174.
- EPTAS for Max Clique on Disks and Unit Balls, with Marthe Bonamy, Édouard Bonnet, Pierre Charbit and Stéphan Thomassé.
FOCS'18, pp. 568-579.
- Reconfiguration of graphs with connectivity constraints, with Arnaud Mary.
WAOA'18, pp. 295-309.
- Parameterized Complexity of Independent Set in H-Free Graphs, with Edouard Bonnet, Pierre Charbit, Stéphan Thomassé and Rémi Watrigant.
IPEC'18, pp. 17:1-17:13.
- Distributed coloring in sparse graphs with fewer colors, with Pierre Aboulker, Marthe Bonamy and Louis Esperet.
PODC'18, pp. 419-425.
- Token Jumping in minor-closed classes, with Arnaud Mary and Aline Parreau.
FCT'17, pp. 136-149.
- Token Sliding on Chordal Graphs, with Marthe Bonamy.
WG'17, pp. 127-139.
- Computing maximum cliques in B_2-EPG graphs, with Marc Heinrich.
WG'17, pp. 140-152.
- On the economic efficiency of the combinatorial clock auction, with Yang Cai, Christof Hunkenschroder and Adrian Vetta.
SODA'16, pp. 1407-1423.
- Welfare and Rationality Guarantees for the Simultaneous Multiple-Round Auction, with Yang Cai and Adrian Vetta.
WINE'15 , pp.216-229.
- Coalition Games on Interaction Graphs: A Horticultural Perspective, with Zhentao Li and Adrian Vetta.
EC'15, pp. 95-112.
- A near-optimal mechanism for impartial selection, with Sergey Norin and Adrian Vetta.
WINE'14, pp. 133-146.
[Bibtex ][Bibtex ]
@inproceedings{BousquetNV14,
author = {N. Bousquet and
S. Norin and
A. Vetta},
title = {A Near-Optimal Mechanism for Impartial Selection},
booktitle = {Web and Internet Economics - 10th, {WINE}
2014. Proceedings},
pages = {133--146},
year = {2014},
url = {http://dx.doi.org/10.1007/978-3-319-13129-0_10},
}
- Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs, with Marin Bougeret, Rodolphe Giroudeau and Rémi Watrigant.
SOFSEM'14, Springer Lecture Notes in Computer Science 8327, pp. 150-161.
[Bibtex ][Bibtex ]
@inproceedings{BougeretBGW14,
author = {M. Bougeret and
N. Bousquet and
R. Giroudeau and
R. Watrigant},
title = {Parameterized Complexity of the Sparsest k-Subgraph Problem
in Chordal Graphs},
booktitle = {SOFSEM},
year = {2014},
pages = {150-161},
ee = {http://dx.doi.org/10.1007/978-3-319-04298-5_14},
}
- Adjacent vertex-distinguishing edge coloring of graphs, with Marthe Bonamy and Hervé Hocquard.
EuroComb'13, CRM Series Volume 16, 2013, pp 313-318 .
- Recoloring bounded treewidth graphs, with Marthe Bonamy.
LAGOS'13, Electronic Notes in Discrete Math. 44: 257-262, 2013.
[Bibtex ][Bibtex ]
@article{BB13,
author = {M. Bonamy and
N. Bousquet},
title = {Recoloring bounded treewidth graphs},
journal = {Electronic Notes in Discrete Mathematics},
volume = {44},
year = {2013},
pages = {257-262},
ee = {http://dx.doi.org/10.1016/j.endm.2013.10.040},
}
- Parameterized Domination in Circle Graphs, with Daniel Gonçalves, George Mertzios, Christophe Paul, Ignasi Sau and Stéphan Thomassé.
WG'12, volume 7551 of Lecture Notes in Computer Science (2012) 308-319.
[Bibtex ][Bibtex ]
@INPROCEEDINGS{BGMPST12,
author = {N. Bousquet and D. Gon\c{c}alves and G. Mertzios and C. Paul and
I. Sau and S. Thomass{\'e}},
title = {Parameterized Domination in Circle Graphs},
booktitle = {WG},
year = {2012},
pages = {308-319},
ee = {http://dx.doi.org/10.1007/978-3-642-34611-8_31}
}
- Multicut is FPT, with Jean Daligault, Stéphan Thomassé.
STOC'11, Proceedings of the 43rd annual ACM symposium on Theory of computing (2011), 459-468.
[Bibtex ][Bibtex ]
@INPROCEEDINGS{BDT11,
author = {N. Bousquet and J. Daligault and S. Thomass{\'e}},
title = {Multicut is {FPT}},
booktitle = {STOC},
year = {2011},
pages = {459-468},
ee = {http://doi.acm.org/10.1145/1993636.1993698}
}
- Equivalence and Inclusion Problem for Strongly Unambiguous Büchi Automata, with Christof Löding.
LATA 2010 , volume 6031 of Lecture Notes in Computer Science, (2010) 118-129.
[Bibtex ][Bibtex ]
@INPROCEEDINGS{BL10,
author = {N. Bousquet and C. L{\"o}ding},
title = {Equivalence and Inclusion Problem for Strongly Unambiguous {B\"u}chi
Automata},
booktitle = {LATA},
year = {2010},
pages = {118-129},
ee = {http://dx.doi.org/10.1007/978-3-642-13089-2_10}
}
-
A Polynomial Kernel for Multicut in Trees, with Jean Daligault, Stéphan Thomassé, Anders Yeo.
STACS'09, (2009) 183-194.
[Bibtex ][Bibtex ]
@INPROCEEDINGS{BousquetDTY09,
author = {N. Bousquet and J. Daligault and S. Thomass{\'e} and A. Yeo},
title = {A Polynomial Kernel for Multicut in Trees},
booktitle = {STACS},
year = {2009},
pages = {183-194},
ee = {http://dx.doi.org/10.4230/LIPIcs.STACS.2009.1824}
}
Programs
- PasTEC - Exact solver for Cluster Editing, with Valentin Bartier, Gabriel Bathie, Marc Heinrich, Théo Pierron, Ulysse Prieto.
PACE Solver Description: PaSTEC - PAths, Stars and Twins to Edit Towards Clusters. IPEC 2021, pp. 29:1-29:4. (Solver ranked 3rd in the Exact track of PACE 2021)
- μSolver - Heuristic solver for Cluster Editing, with Valentin Bartier, Gabriel Bathie, Marc Heinrich, Théo Pierron, Ulysse Prieto.
PACE Solver Description: μSolver - Heuristic Track. IPEC 2021, pp. 33:1-33:3. (Solver ranked 3rd in the Heuristic track of PACE 2021)
Preprints
- A note on highly connected K_{2,l}-minor free graphs, with Théo Pierron, Alexandra Wesolek, submitted.
- Digraph redicolouring, with Frédéric Havet, Nicolas Nisse, Lucas Picasarri-Arrieta and Amadeus Reinald, submitted.
- A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems, with Amer E. Mouawad, Naomi Nishimura and Sebastian Siebertz, submitted.
- Square coloring planar graphs with automatic discharging, with Lucas de Meyer, Quentin Deschamps, Théo Pierron, submitted.
- Short and local transformations between (Δ+1)-colorings, with Laurent Feuilloley, Marc Heinrich, Mikaël Rabie, submitted.
- Reconfiguration of independent sets in cographs, with Marthe Bonamy, submitted.
Misc
- Local certification of MSO properties for bounded treedepth graphs, with Laurent Feuilloley and Théo Pierron, preprint.
(see the updated version "What can be certified compactly?")
- Surfaces have (asymptotic) dimension 2, with
Marthe Bonamy, Louis Esperet, Carla Groenland, François Pirot and Alex Scott, preprint.
(see the updated paper "Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces")
- On the chromatic number of wheel-free graphs with no large bipartite graphs, with Stéphan Thomassé.
- Shapley value on matching games for trees.
(Manuscript needing polishing)
- Metric dimension on sparse graphs and its applications to zero forcing sets with Quentin Deschamps, Aline Parreau and Ignacio M. Pelayo.
(An anonymous reviewer remarked that the main result is implied by another recent result.)
Thesis:
- Hitting Sets: VC-dimension and Multicut.
PhD thesis.
- Vapnik-Chervonenkis Dimension.
Master Thesis.
- Le problème de l'équivalence pour les automates de Büchi fortement non ambigüs.
First year of Master thesis. (in French) (slides: french, english).
- Un noyau polynomial pour Multicut in Trees
Undergrad Thesis, in french. (slides in french).
- Distributed algorithms (Master 2, ENS Lyon), Fall 2023-...
- Algorithmique avancée (Master 2, Université Lyon 1), Fall 2021-2023
- MOD4.4: Recherche opérationnelle (3rd year Ecole Centrale de Lyon, Cours TD/TP, 16h), Fall 2016-... .
- Graphs and Discrete Structure (Master ORCO, Grenoble, Cours, 9h), Fall 2018. (Lecture Part 1, Part 2, Exercises).
- Optimization and Approximation (Master 1, ENS Lyon), Fall 2017, 2018 and 2019.
- Introduction to Economic Game Theory (Doctoral course, Grenoble, 6h), Fall 2018.
- Combinatorial Optimization (Master ORCO, Grenoble, Cours, 9h), Fall 2016-2017.
- INF-TC1: Introduction to algorithms (1st year Ecole Centrale de Lyon, TD/TP, 84h), Fall 2015 and Spring 2016.
- INF-TC2: Object-oriented programming (1st year Ecole Centrale de Lyon, TD/TP, 60h), Fall 2015 and Spring 2016.
- INF-TC3: Web and Database Project (1st year Ecole Centrale de Lyon, TD/TP, 48h), Fall 2015 and Spring 2016.
- Mathematical Programming (Lectures, 42h), Fall 2014.
- Systemes (L3, TD/TP Université Montpellier II, 34h), Fall 2013.
- Introduction Systeme et Reseaux (M1, TP Université Montpellier II, 36h), Fall 2013
- Introduction à l'algorithmique et la programmation (L1 TD/TP, Université Montpellier II, 52h), Fall 2012.
- Algorithmique des graphes (L3 TP, Université Montpellier II, 12h), Fall 2012.
- Programmation en C (TP, IUT Béziers, 40h), Spring 2012.
- C2I (L1 TP, Université Montpellier II, 15h), Fall 2011.
- Initiation à la programmation (TP, IUT Montpellier, 18h), Fall 2011.
You can find the details and the slides of all my talks there. In this page, I just mention a couple of recent talks (to see the slides, click on the picture ):
- Recoloring, from statistical physics to combinatorics, One day Discrete Structure Meeting, ENS Lyon, June, 15th, 2018.
- Exact distance coloring in trees, ANR DISTANCIA, Marseille, April, 11th, 2018.
- Token Sliding on Chordal Graphs, BIRS Workshop, Banff, Canada, January 2017.
- Discrete Maths and Optimization Seminar, McGill, September, 29th, 2014, Clique, stable sets and chromatic number.
- Clermont-Ferrand, March, 28th, 2013, Hitting sets and VC-dimension.
Grants
I am, or have been PI of the following projects:
- ANR Project GrR (Graph Reconfiguration). Budget: 200k euros. Duration: 4 years (2019-2023) \\
- DATCORE (Development of Algorithmic Techniques on Combinatorial Reconfiguration). Bilateral project with Japan, under the PHC Sakura Program. Budget: 14k euros + 2M yens. Duration: 2 years (2018-2019).
The japonese PI is Takehiro Ito.
- IRS Project "RAGE" (Reconfiguration: Algorithms, Generation and Enumeration). Budget: 15k euros. Duration: 2 years (2018-2019).
- INS2I JCJC project ECSG (Combinatorial Auctions and Graph Structure). Budget: 10k euros. Duration: 1 year (2017).
You may have seen me there:
Here is a complete list of events I attended to.