Browsing Bergen Open Research Archive by Author "Bergougnoux, Benjamin"

Now showing items 1-4 of 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 ...

    • More Applications of the d-Neighbor Equivalence: Acyclicity and Connectivity Constraints 

      Bergougnoux, Benjamin; Kanté, Mamadou Moustapha (Journal article; Peer reviewed, 2021)
      In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced ...

    • On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters 

      Høgemo, Svein; Bergougnoux, Benjamin; Brandes, Ulrik; Paul, Christophe; Telle, Jan Arne (Journal article; Peer reviewed, 2021)
      The minimum height of vertex and edge partition trees are well-studied graph parameters known as, for instance, vertex and edge ranking number. While they are NP-hard to determine in general, linear-time algorithms exist ...

    • Towards a Polynomial Kernel for Directed Feedback Vertex Set 

      Bergougnoux, Benjamin; Eiben, Eduard; Ganian, Robert; Ordyniak, Sebastian; Ramanujan, M. S. (Journal article; Peer reviewed, 2020)
      In the DIRECTED FEEDBACK VERTEX SET (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. ...