21 citations · 83 across the 14 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.DS2009★ 1 cited
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…
cs.CC2009★ 1 cited
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…