Iterative compression and exact algorithms

作者：Fomin Fedor V; Gaspers Serge; Kratsch Dieter; Liedloff Mathieu^*; Saurabh Saket

来源：Theoretical Computer Science, 2010, 411(7-9): 1045-1053.

DOI：10.1016/j.tcs.2009.11.012

• Exponential time algorithms
• Graph algorithms
• Independent set
• Hitting set
• Induced cluster
• Fixed parameter algorithms
• Iterative compression

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.

• 单位
  常州工学院