Exact algorithms for NP-hard problems : A survey

G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

478 Citations (Scopus)
3 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationCombinatorial Optimization - Eureka! You shrink! Papers dedicated to Jack Edmonds. (5th International Workshop, Aussois, France, March 2001, Revised papers)
EditorsM. Jünger, G. Reinelt, G. Rinaldi
Place of PublicationBerlin
PublisherSpringer
Pages185-207
DOIs
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
Volume2570
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Exact algorithms for NP-hard problems : A survey'. Together they form a unique fingerprint.

Cite this