Exact Algorithms for NP-Hard Problems: A Survey
Exact Algorithms for NP-Hard Problems: A Survey
复制标题
DOI：
10.1007/3-540-36478-1_17
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
G. Woeginger
中科院分区：
文献类型：
--
作者：
G. Woeginger
讨论了np完全问题的快速指数时间解。我们调查了已知的结果和方法，我们提供了文献的指针，并讨论了该领域的几个开放问题。讨论的np完全问题包括旅行商问题、优先约束下的调度、可满足性、背包、图着色、图中的独立集、图的带宽等等。
We discuss fast exponential time solutions for NP-complete problems. We survey known results and approaches, we provide pointers to the literature, and we discuss several open problems in this area. The list of discussed NP-complete problems includes the travelling salesman problem, scheduling under precedence constraints, satisfiability, knapsack, graph coloring, independent sets in graphs, bandwidth of a graph, and many more.