114 citations · 306 across the 50 of their papers we have counts for
6 papers · 1 filter
On Kernelization and Approximation for the Vector Connectivity Problem
Stefan Kratsch, Manuel Sorge
In the Vector Connectivity problem we are given an undirected graph , a demand function , and an integer . The question is whether there exi…
Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem
Gregory Gutin, Stefan Kratsch, Magnus Wahlström
The Workflow Satisfiability Problem (WSP) is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defined by…
The Minimum Feasible Tileset problem
Yann Disser, Stefan Kratsch, Manuel Sorge
We introduce and study the Minimum Feasible Tileset problem: Given a set of symbols and subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols (t…
Streaming Kernelization
Stefan Fafianie, Stefan Kratsch
Kernelization is a formalization of preprocessing for combinatorially hard problems. We modify the standard definition for kernelization, which allows any polynomial-time algorithm…
Characterizing width two for variants of treewidth
Hans L. Bodlaender, Vincent J. C. Kreuzen, Stefan Kratsch +2
In this paper, we consider the notion of \emph{special treewidth}, recently introduced by Courcelle\cite{Courcelle2012}. In a special tree decomposition, for each vertex in a g…
Finding Shortest Paths between Graph Colourings
Matthew Johnson, Dieter Kratsch, Stefan Kratsch +2
The -colouring reconfiguration problem asks whether, for a given graph , two proper -colourings and of , and a positive integer , there exists a sequence…