Exact algorithms for NP-hard problems: A survey

Gerhard Woeginger

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

343 Citations (Scopus)

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!
Subtitle of host publicationPapers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5–9, 2001 Revised Papers
EditorsM. Junger, G. Reinelt, G. Rinaldi
PublisherSpringer
Pages185-207
ISBN (Print)3-540-00580-3
DOIs
Publication statusPublished - 2003
EventJack Edmonds 5th International Workshop 2001 - Aussois, France
Duration: 5 Mar 20019 Mar 2001
Conference number: 5

Publication series

NameLecture notes in computer science
Volume2570
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

WorkshopJack Edmonds 5th International Workshop 2001
CountryFrance
CityAussois
Period5/03/019/03/01

Keywords

  • METIS-213358

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

  • Cite this

    Woeginger, G. (2003). Exact algorithms for NP-hard problems: A survey. In M. Junger, G. Reinelt, & G. Rinaldi (Eds.), Combinatorial Optimization -- Eureka, you shrink!: Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5–9, 2001 Revised Papers (pp. 185-207). (Lecture notes in computer science; Vol. 2570). Springer. https://doi.org/10.1007/3-540-36478-1_17