Techniques for Practical Fixed-Parameter Algorithms
Techniques for Practical Fixed-Parameter Algorithms
复制标题
实用固定参数算法技术
DOI：
10.1093/comjnl/bxm040
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
S. Wernicke
中科院分区：
文献类型：
--
作者：
Falk Hüffner;R. Niedermeier;S. Wernicke
固定参数方法是一种用于解决组合性（主要是NP）问题的算法设计技术。对于其中一些问题，它可能导致算法既有效又可以保证找到最佳解决方案。为了关注他们在实践中解决NP硬问题问题的应用，我们调查了三种主要技术，以开发固定参数算法，即：内核化（可证明性能保证的数据降低），深度的搜索树和一种称为迭代压缩的新技术。我们的讨论与几个具体案例研究有关，并为该领域的各种挑战提供了指示。
The fixed-parameter approach is an algorithm design technique for solving combinatorially hard (mostly NP-hard) problems. For some of these problems, it can lead to algorithms that are both efficient and yet at the same time guaranteed to find optimal solutions. Focusing on their application to solving NP-hard problems in practice, we survey three main techniques to develop fixed-parameter algorithms, namely: kernelization (data reduction with provable performance guarantee), depthbounded search trees and a new technique called iterative compression. Our discussion is circumstantiated by several concrete case studies and provides pointers to various current challenges in the field.
影响因子：
14.9
作者：
Stojanovic, N;Florea, L;Hardison, R
通讯作者：
Hardison, R