Artículo de revista
Iterative Compression and Exact Algorithms
Autor
Fomin, Fedor V.
Gaspers, Serge
Kratsch, Dieter
Liedloff, Mathieu
Saurabh, Saket
Institución
Resumen
Iterative Compression has recently led to a number of breakthroughs
in parameterized complexity. Here, we show that the technique can
also be useful in the design of exact exponential time algorithms to
solve NP-hard problems. We exemplify our ndings with algorithms
for the Maximum Independent Set problem, a parameterized and
a counting version of d-Hitting Set and the Maximum Induced
Cluster Subgraph problem.