114 citations · 306 across the 50 of their papers we have counts for
4 papers · 2 filters
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…
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…