121 citations · 375 across the 53 of their papers we have counts for
4 papers · 1 filter
A Planar Linear Arboricity Conjecture
Marek Cygan, Lukasz Kowalik, Borut Luzar
The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. In 1984, Akiyama et al. stated the Linear Arboricity Conjecture (LAC…
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…