Blar i Bergen Open Research Archive på forfatter "Bonnet, Édouard"

Viser treff 1-4 av 4

    • Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth 

      Bergougnoux, Benjamin; Bonnet, Édouard; Brettell, Nick; Kwon, O-Joung (Journal article; Peer reviewed, 2020)
      The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time 2^𝒪(tw)n^𝒪(1), for Feedback Vertex Set and connected versions of ...

    • Metric Dimension Parameterized By Treewidth 

      Bonnet, Édouard; Purohit, Nidhi (Journal article; Peer reviewed, 2021)
      A resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The METRIC DIMENSION problem asks for a resolving set of minimum size, and in its decision form, ...

    • Parameterized streaming algorithms for min-ones d-SAT 

      Agrawal, Akanksha; Bonnet, Édouard; Curticapean, Radu; Miltzow, Tillmann; Saurabh, Saket; Biswas, Arindam; Brettell, Nick; Marx, Dániel; Raman, Venkatesh (Journal article; Peer reviewed, 2019)
      In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has ...

    • Treewidth is NP-Complete on Cubic Graphs 

      Bodlaender, Hans L.; Bonnet, Édouard; Jaffke, Lars; Knop, Dusan; Lima, Paloma Thome de; Milanič, Martin; Ordyniak, Sebastian; Pandey, Sukanya; Suchy, Ondrey (Journal article; Peer reviewed, 2023)
      In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new ...