21 citations · 83 across the 14 of their papers we have counts for
4 papers · 1 filter
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…
Channel Assignment via Fast Zeta Transform
Marek Cygan, Łukasz Kowalik
We show an O*((l+1)^n)-time algorithm for the channel assignment problem, where l is the maximum edge weight. This improves on the previous O*((l+2)^n)-time algorithm by Kral, as w…
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…