Exact algorithms for NP-hard problems: a survey

@article{citeulike:489763, abstract = {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.}, address = {New York, NY, USA}, author = {Woeginger, Gerhard J. }, citeulike-article-id = {489763}, isbn = {3540005803}, keywords = {algorithm, theory}, pages = {185--207}, posted-at = {2006-04-07 20:26:55}, priority = {2}, publisher = {Springer-Verlag New York, Inc.}, title = {Exact algorithms for NP-hard problems: a survey}, url = {http://portal.acm.org/citation.cfm?id=885927}, year = {2003} }

TY - JOUR ID - citeulike:489763 L3 - citeulike-article-id:489763 TI - Exact algorithms for NP-hard problems: a survey SP - 185 EP - 207 AD - New York, NY, USA PB - Springer-Verlag New York, Inc. SN - 3540005803 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. KW - algorithm KW - theory AU - Woeginger, Gerhard PY - 2003/// UR - http://portal.acm.org/citation.cfm?id=885927 ER -