121 citations · 375 across the 53 of their papers we have counts for
Showing 2017Show 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.DS2017
Improving TSP tours using dynamic programming over tree decomposition
Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
Given a traveling salesman problem (TSP) tour in graph a -move is an operation which removes edges from , and adds edges of so that a new tour is for…
cs.DS2017★ 33 cited
On problems equivalent to (min,+)-convolution
Marek Cygan, Marcin Mucha, Karol Węgrzycki +1
In recent years, significant progress has been made in explaining the apparent hardness of improving upon the naive solutions for many fundamental polynomially solvable problems. T…