19 citations · 218 across the 100 of their papers we have counts for
3 papers · 1 filter
Fast Approximation in Subspaces by Doubling Metric Decomposition
Marek Cygan, Lukasz Kowalik, Marcin Mucha +2
In this paper we propose and study a new complexity model for approximation algorithms. The main motivation are practical problems over large data sets that need to be solved many…
Beyond O*(2^n) in domination-type problems
Marek Cygan, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk
In this paper we provide algorithms faster than O*(2^n) for several NP-complete domination-type problems. More precisely, we provide: an algorithm for CAPACITATED DOMINATING SET th…
Even Faster Exact Bandwidth
Marek Cygan, Marcin Pilipczuk
We deal with exact algorithms for Bandwidth, a long studied NP-hard problem. For a long time nothing better than the trivial O*(n!) exhaustive search was known. In 2000, Feige an K…