| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 439062 | Theoretical Computer Science | 2010 | 9 Pages |
Abstract
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 findings 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
