vix.ing · top · new · best · stats · spec

Bonnet, Édouard

  1. Twin-width I: tractable FO model checking
    2020/04/30 by Bonnet, Édouard, Kim, Eun Jung, Thomassé, Stéphan +1 · 11 citations
    #68Q25 #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
  2. Twin-width IV: ordered graphs and matrices
    2021/02/05 by Édouard Bonnet, Bonnet, Édouard, Ugo Giocanti +9 · 7 citations
    Engineering · Computer Science · #graph theory and CDMA systems #semigroups and automata theory #Coding theory and cryptography
  3. Twin-width II: small classes
    2020/06/17 by Édouard Bonnet, Colin Geniet, Bonnet, Édouard +7 · 7 citations
    Computer Science · Mathematics · #05C30 #05C48 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Logic in Computer Science (cs.LO)
  4. Complexity of Token Swapping and its Variants
    2016/07/26 by Bonnet, Édouard, Miltzow, Tillmann, Rzążewski, Paweł · 4 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  5. Fixed-parameter Approximability of Boolean MinCSPs
    2016/01/19 by Bonnet, Édouard, Egri, László, Lin, Bingkai +1 · 3 citations
    #68Q17 #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences
  6. Twin-width VI: the lens of contraction sequences
    2021/10/30 by Bonnet, Édouard, Kim, Eun Jung, Reinald, Amadeus +1 · 4 citations
    #05C85 #68R10 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)
  7. Parameterized Complexity of Independent Set in H-Free Graphs
    2018/10/10 by Bonnet, Édouard, Bousquet, Nicolas, Charbit, Pierre +2 · 2 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  8. Twin-width and polynomial kernels
    2021/07/06 by Bonnet, Édouard, Kim, Eun Jung, Reinald, Amadeus +2 · 3 citations
    #05C85 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics
  9. Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
    2022/02/24 by Édouard Bonnet, O‐joung Kwon, Bonnet, Édouard +3 · 3 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
  10. Deciding twin-width at most 4 is NP-complete
    2021/12/16 by Bergé, Pierre, Bonnet, Édouard, Déprés, Hugues · 3 citations
    #68Q17 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics
  11. Parameterized Intractability of Even Set and Shortest Vector Problem
    2019/09/04 by Bhattacharyya, Arnab, Bonnet, Édouard, Egri, László +5 · 2 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  12. Optimality program in segment and string graphs
    2017/12/24 by Bonnet, Édouard, Rzążewski, Paweł · 2 citations
    #68Q17 #68Q25 #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #G.2.2
  13. Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
    2023/12/13 by Édouard Bonnet, Jędrzej Hodor, Bonnet, Édouard +5 · 3 citations
    Computer Science · Mathematics · #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory
  14. Twin-width VIII: delineation and win-wins
    2022/04/01 by Édouard Bonnet, Dibyayan Chakraborty, Bonnet, Édouard +9 · 2 citations
    Computer Science · Engineering · #05C75 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO) #graph theory and CDMA systems #semigroups and automata theory
  15. Twin-width VII: groups
    2022/04/26 by Édouard Bonnet, Colin Geniet, Bonnet, Édouard +5 · 2 citations
    Computer Science · Mathematics · #05C25 (Primary) 20F65 #05C30 (Secondary) #Cellular Automata and Applications #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #G.2.2 #Geometric and Algebraic Topology #Group Theory (math.GR)
  16. On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
    2014/12/03 by Abu-Khzam, Faisal N., Bonnet, Édouard, Sikora, Florian · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  17. An Approximation Algorithm for the Art Gallery Problem
    2016/07/19 by Bonnet, Édouard, Miltzow, Tillmann · 1 citation
    #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  18. QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
    2017/12/13 by Bonnet, Édouard, Giannopoulos, Panos, Kim, Eun Jung +2 · 1 citation
    #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2
  19. On the Parameterized Complexity of Red-Blue Points Separation
    2017/10/02 by Bonnet, Édouard, Giannopoulos, Panos, Lampis, Michael · 1 citation
    #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences
  20. EPTAS for Max Clique on Disks and Unit Balls
    2018/03/05 by Bonamy, Marthe, Bonnet, Édouard, Bousquet, Nicolas +2 · 1 citation
    #68Q25 #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences
  21. Metric Dimension Parameterized by Treewidth
    2019/07/18 by Bonnet, Édouard, Purohit, Nidhi · 1 citation
    #68Q17 #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
  22. Maximum Clique in Disk-Like Intersection Graphs
    2020/03/05 by Bonnet, Édouard, Grelier, Nicolas, Miltzow, Tillmann · 1 citation
    #68Q25 #68U05 #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
  23. Treewidth Inapproximability and Tight ETH Lower Bound
    2024/06/17 by Bonnet, Édouard · 2 citations
    #68Q17 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics
  24. Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
    2022/02/25 by Bonnet, Édouard, Dreier, Jan, Gajarský, Jakub +4 · 1 citation
    #05C85 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)
  25. Twin-width can be exponential in treewidth
    2022/04/15 by Bonnet, Édouard, Déprés, Hugues · 1 citation
    #05C05 #05C75 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
  26. Twin-width V: linear minors, modular counting, and matrix multiplication
    2022/09/24 by Bonnet, Édouard, Giocanti, Ugo, de Mendez, Patrice Ossona +1 · 1 citation
    #68W01 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)
  27. Mim-Width is paraNP-complete
    2025/01/10 by Bergougnoux, Benjamin, Bonnet, Édouard, Duron, Julien · 2 citations
    #68Q27 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics
  28. Factoring Pattern-Free Permutations into Separable ones
    2023/08/06 by Bonnet, Édouard, Bourneuf, Romain, Geniet, Colin +1 · 1 citation
    #05A05 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #Logic in Computer Science (cs.LO)
  29. Symmetric-Difference (Degeneracy) and Signed Tree Models
    2024/05/15 by Bonnet, Édouard, Duron, Julien, Sylvester, John +1 · 1 citation
    #05C05 #05C78 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics
  30. Induced Disjoint Paths Without an Induced Minor
    2025/02/07 by Aboulker, Pierre, Bonnet, Édouard, Picavet, Timothé +1 · 1 citation
    #68Q25 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics
  31. Every Graph is Essential to Large Treewidth
    2025/02/20 by Alecu, Bogdan, Bonnet, Édouard, Villafana, Pedro Bureo +1 · 1 citation
    #05C75 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2