Édouard Bonnet

ORCID

Publication Activity (10 Years)

Years Active: 2014-2024
Publications (10 Years): 135

Top Venues

Paris Dauphine University, France (PHD)

Education History

Paris Dauphine University, France

PHD

Publications

Édouard Bonnet, Carl Feghali, Stéphan Thomassé, Nicolas Trotignon
Graphs without a 3-connected subgraph are 4-colorable. CoRR (2024)
Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä, Aline Parreau
Neighbourhood complexity of graphs of bounded twin-width. Eur. J. Comb. 115 (2024)
Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä, Aline Parreau
Neighbourhood complexity of graphs of bounded twin-width. CoRR (2023)
Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer
Maximum Matchings in Geometric Intersection Graphs. Discret. Comput. Geom. 70 (3) (2023)
Édouard Bonnet, Jedrzej Hodor, Tuukka Korhonen, Tomás Masarík
Treewidth is Polynomial in Maximum Degree on Graphs Excluding a Planar Induced Minor. CoRR (2023)
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý
Treewidth Is NP-Complete on Cubic Graphs. IPEC (2023)
Édouard Bonnet, Hugues Déprés
Twin-width can be exponential in treewidth. J. Comb. Theory, Ser. B 161 (2023)
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Stéphan Thomassé
Twin-Width V: Linear Minors, Modular Counting, and Matrix Multiplication. STACS (2023)
Pierre Bergé, Édouard Bonnet, Hugues Déprés, Rémi Watrigant
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width. STACS (2023)
Édouard Bonnet, Romain Bourneuf, Colin Geniet, Stéphan Thomassé
Factoring Pattern-Free Permutations into Separable ones. CoRR (2023)
Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, Maksim Zhukovskii
Tight bounds on adjacency labels for monotone graph classes. CoRR (2023)
Édouard Bonnet, Dibyayan Chakraborty, Julien Duron
Cutting Barnette Graphs Perfectly is Hard. WG (2023)
Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, Florian Sikora
Grundy Coloring and Friends, Half-Graphs, Bicliques. Algorithmica 85 (1) (2023)
Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, Alexandra Wesolek
Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄. ESA (2023)
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý
Treewidth is NP-Complete on Cubic Graphs (and related results). CoRR (2023)
Édouard Bonnet, Dibyayan Chakraborty, Julien Duron
Cutting Barnette graphs perfectly is hard. CoRR (2023)
Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, Maksim Zhukovskii
Small But Unwieldy. CoRR (2023)
Édouard Bonnet, Julien Duron
Stretch-width. CoRR (2023)
Édouard Bonnet, Julien Duron
PACE Solver Description: RedAlert - Heuristic Track. IPEC (2023)
Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, Alexandra Wesolek
. CoRR (2023)
Édouard Bonnet, Julien Duron
Stretch-Width. IPEC (2023)
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant
Twin-width and Polynomial Kernels. Algorithmica 84 (11) (2022)
Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Torunczyk
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth. LICS (2022)
Pierre Bergé, Édouard Bonnet, Hugues Déprés
Deciding Twin-Width at Most 4 Is NP-Complete. ICALP (2022)
Édouard Bonnet
. ACM Trans. Algorithms 18 (2) (2022)
Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Torunczyk
Model Checking on Interpretations of Classes of Bounded Local Cliquewidth. CoRR (2022)
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Torunczyk
Twin-width IV: ordered graphs and matrices. STOC (2022)
Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, Stéphan Thomassé
Twin-Width VIII: Delineation and Win-Wins. IPEC (2022)
Édouard Bonnet, Hugues Déprés
Twin-width can be exponential in treewidth. CoRR (2022)
Édouard Bonnet, Colin Geniet, Romain Tessera, Stéphan Thomassé
Twin-width VII: groups. CoRR (2022)
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Stéphan Thomassé
Twin-width V: linear minors, modular counting, and matrix multiplication. CoRR (2022)
Pierre Bergé, Édouard Bonnet, Hugues Déprés, Rémi Watrigant
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width. CoRR (2022)
Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, Stéphan Thomassé
Twin-width VIII: delineation and win-wins. CoRR (2022)
Édouard Bonnet, O-joung Kwon, David R. Wood
Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond). CoRR (2022)
Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek
Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. CoRR (2022)
Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
Twin-width I: Tractable FO Model Checking. J. ACM 69 (1) (2022)
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé
Twin-width VI: the lens of contraction sequences. SODA (2022)
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora, Stéphan Thomassé
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs. CoRR (2021)
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
Parameterized Intractability of Even Set and Shortest Vector Problem. J. ACM 68 (3) (2021)
Édouard Bonnet, Nidhi Purohit
Metric Dimension Parameterized By Treewidth. Algorithmica 83 (8) (2021)
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora, Stéphan Thomassé
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs. J. ACM 68 (2) (2021)
Pierre Bergé, Édouard Bonnet, Hugues Déprés
Deciding twin-width at most 4 is NP-complete. CoRR (2021)
Édouard Bonnet, Sergio Cabello, Bojan Mohar, Hebert Pérez-Rosés
The Inverse Voronoi Problem in Graphs II: Trees. Algorithmica 83 (5) (2021)
Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Stéphan Thomassé
Twin-width IV: low complexity matrices. CoRR (2021)
Édouard Bonnet
Inapproximability of Diameter in Super-Linear Time: Beyond the 5/3 Ratio. STACS (2021)
Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
Twin-width III: Max Independent Set, Min Dominating Set, and Coloring. ICALP (2021)
Édouard Bonnet, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz, Stéphan Thomassé
Twin-width and permutations. CoRR (2021)
Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
Twin-width II: small classes. SODA (2021)
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé
Twin-width VI: the lens of contraction sequences. CoRR (2021)
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant
Twin-Width and Polynomial Kernels. IPEC (2021)
Édouard Bonnet
. CoRR (2021)
Édouard Bonnet, Sergio Cabello
The complexity of mixed-connectivity. Ann. Oper. Res. 307 (1) (2021)
Édouard Bonnet
4 vs 7 Sparse Undirected Unweighted Diameter is SETH-Hard at Time n^{4/3}. ICALP (2021)
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant
Twin-width and polynomial kernels. CoRR (2021)
Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow
Maximum Clique in Disk-Like Intersection Graphs. CoRR (2020)
Édouard Bonnet, Pawel Rzazewski, Florian Sikora
Designing RNA Secondary Structures Is Hard. J. Comput. Biol. 27 (3) (2020)
Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
Twin-width II: small classes. CoRR (2020)
Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran, Rémi Watrigant
An algorithmic weakening of the Erdős-Hajnal conjecture. CoRR (2020)
Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
Twin-width I: tractable FO model checking. CoRR (2020)
Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant
Parameterized Complexity of Independent Set in H-Free Graphs. Algorithmica 82 (8) (2020)
Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran, Rémi Watrigant
An Algorithmic Weakening of the Erdős-Hajnal Conjecture. ESA (2020)
Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, Florian Sikora
Grundy Coloring & Friends, Half-Graphs, Bicliques. STACS (2020)
Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell, O-joung Kwon
Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth. IPEC (2020)
Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow
Maximum Clique in Disk-Like Intersection Graphs. FSTTCS (2020)
Édouard Bonnet, Sergio Cabello, Bojan Mohar, Hebert Pérez-Rosés
The Inverse Voronoi Problem in Graphs I: Hardness. Algorithmica 82 (10) (2020)
Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
Twin-width III: Max Independent Set and Coloring. CoRR (2020)
Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, Florian Sikora
Grundy Coloring & friends, Half-Graphs, Bicliques. CoRR (2020)
Édouard Bonnet, Sergio Cabello
The Complexity of Mixed-Connectivity. CoRR (2020)
Édouard Bonnet, Tillmann Miltzow
Parameterized Hardness of Art Gallery Problems. ACM Trans. Algorithms 16 (4) (2020)
Édouard Bonnet
Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio. CoRR (2020)
Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant
Twin-width I: tractable FO model checking. FOCS (2020)
Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell, O-joung Kwon
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth. CoRR (2020)
Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer
Maximum Matchings in Geometric Intersection Graphs. STACS (2020)
Édouard Bonnet, Sergio Cabello, Wolfgang Mulzer
Maximum Matchings in Geometric Intersection Graphs. CoRR (2019)
Édouard Bonnet, Panos Giannopoulos
Orthogonal Terrain Guarding is NP-complete. J. Comput. Geom. 10 (2) (2019)
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
Parameterized Intractability of Even Set and Shortest Vector Problem. Electron. Colloquium Comput. Complex. 26 (2019)
Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, Saket Saurabh
Parameterized Streaming Algorithms for Min-Ones d-SAT. FSTTCS (2019)
Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, Lukasz Kowalik
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP. CoRR (2019)
Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, Rémi Watrigant
When Maximum Stable Set Can Be Solved in FPT Time. ISAAC (2019)
Édouard Bonnet, Nick Brettell, O-joung Kwon, Dániel Marx
Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms. Algorithmica 81 (10) (2019)
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
Parameterized Intractability of Even Set and Shortest Vector Problem. CoRR (2019)
Édouard Bonnet, Pawel Rzazewski
Optimality Program in Segment and String Graphs. Algorithmica 81 (7) (2019)
Édouard Bonnet, Diana-Elena Falamas, Rémi Watrigant
Constraint Generation Algorithm for the Minimum Connectivity Inference Problem. CoRR (2019)
Édouard Bonnet, Diana-Elena Falamas, Rémi Watrigant
Constraint Generation Algorithm for the Minimum Connectivity Inference Problem. SEA² (2019)
Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, Rémi Watrigant
When Maximum Stable Set can be solved in FPT time. CoRR (2019)
Édouard Bonnet, Nidhi Purohit
Metric Dimension Parameterized by Treewidth. IPEC (2019)
Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, Lukasz Kowalik
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP. ESA (2019)
Édouard Bonnet, Nidhi Purohit
Metric Dimension Parameterized by Treewidth. CoRR (2019)
Édouard Bonnet, Florian Sikora
The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration. IPEC (2018)
Édouard Bonnet, Pawel Rzazewski, Florian Sikora
Designing RNA Secondary Structures Is Hard. RECOMB (2018)
Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos, Georgios Stamoulis
Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs. Discret. Optim. 27 (2018)
Édouard Bonnet, Florent Foucaud, Eun Jung Kim, Florian Sikora
Complexity of Grundy coloring and its variants. Discret. Appl. Math. 243 (2018)
Édouard Bonnet, Michael Lampis, Vangelis Th. Paschos
Time-approximation trade-offs for inapproximable problems. J. Comput. Syst. Sci. 92 (2018)
Édouard Bonnet, Sergio Cabello, Bojan Mohar, Hebert Pérez-Rosés
The inverse Voronoi problem in graphs. CoRR (2018)
Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant
Parameterized Complexity of Independent Set in H-Free Graphs. CoRR (2018)
Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs. SoCG (2018)
Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant
Parameterized Complexity of Independent Set in H-Free Graphs. IPEC (2018)
Édouard Bonnet, Pawel Rzazewski
Optimality Program in Segment and String Graphs. WG (2018)
Marthe Bonamy, Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé
EPTAS for Max Clique on Disks and Unit Balls. CoRR (2018)
Édouard Bonnet, Panos Giannopoulos
Orthogonal Terrain Guarding is NP-complete. SoCG (2018)

Édouard Bonnet.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Édouard Bonnet