TY - GEN
T1 - Exact algorithms for NP-hard problems : A survey
AU - Woeginger, G.J.
PY - 2003
Y1 - 2003
N2 - 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.
AB - 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.
U2 - 10.1007/3-540-36478-1_17
DO - 10.1007/3-540-36478-1_17
M3 - Conference contribution
T3 - Lecture Notes in Computer Science
SP - 185
EP - 207
BT - Combinatorial Optimization - Eureka! You shrink! Papers dedicated to Jack Edmonds. (5th International Workshop, Aussois, France, March 2001, Revised papers)
A2 - Jünger, M.
A2 - Reinelt, G.
A2 - Rinaldi, G.
PB - Springer
CY - Berlin
ER -