121 citations · 375 across the 53 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2017
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
Parinya Chalermsook, Marek Cygan, Guy Kortsarz +4
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable…
cs.CC2015
Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
Ivan Bliznets, Marek Cygan, Pawel Komosa +2
In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper Interval Completion, Threshold Completion, and…
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…