9 citations · 9 across the 3 of their papers we have counts for
3 papers
On Multiway Cut parameterized above lower bounds
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk +1
In this paper we consider two above lower bound parameterizations of the Node Multiway Cut problem - above the maximum separating cut and above a natural LP-relaxation - and prove…
Solving connectivity problems parameterized by treewidth in single exponential time
Marek Cygan, Jesper Nederlof, Marcin Pilipczuk +3
For the vast majority of local graph problems standard dynamic programming techniques give c^tw V^O(1) algorithms, where tw is the treewidth of the input graph. On the other hand,…
Approximation Algorithms for Union and Intersection Covering Problems
Marek Cygan, Fabrizio Grandoni, Stefano Leonardi +3
In a classical covering problem, we are given a set of requests that we need to satisfy (fully or partially), by buying a subset of items at minimum cost. For example, in the k-MST…