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. ...