Browsing Bergen Open Research Archive by Author "Kratsch, Dieter"
Now showing items 1-4 of 4
-
Enumerating minimal connected dominating sets in graphs of bounded chordality
Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter (Peer reviewed; Journal article, 2015)Listing, generating or enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration ... -
Exact algorithms for treewidth and minimum fill-in
Fomin, Fedor; Todinca, Ioan; Kratsch, Dieter; Villanger, Yngve (Journal article, 2006) -
A Note on Exact Algorithms for Vertex Ordering Problems on Graphs
Bodlaender, Hans L.; Fomin, Fedor; Koster, Arie M.C.A.; Kratsch, Dieter; Thilikos, Dimitrios M. (Peer reviewed; Journal article, 2011-01-21)In this note, we give a proof that several vertex ordering problems can be solved in O ∗(2 n ) time and O ∗(2 n ) space, or in O ∗(4 n ) time and polynomial space. The algorithms generalize algorithms for the Travelling ... -
Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
Golovach, Petr; Komusiewicz, Christian; Kratsch, Dieter; Le, Van Bang (Journal article; Peer reviewed, 2021)An enumeration kernel as defined by Creignou et al. (2017) [11] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a ...