Exact algorithms for NP-hard problems : A survey

G.J. Woeginger

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

503 Citaten (Scopus)
6 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
TitelCombinatorial Optimization - Eureka! You shrink! Papers dedicated to Jack Edmonds. (5th International Workshop, Aussois, France, March 2001, Revised papers)
RedacteurenM. Jünger, G. Reinelt, G. Rinaldi
Plaats van productieBerlin
UitgeverijSpringer
Pagina's185-207
DOI's
StatusGepubliceerd - 2003

Publicatie series

NaamLecture Notes in Computer Science
Volume2570
ISSN van geprinte versie0302-9743

Vingerafdruk

Duik in de onderzoeksthema's van 'Exact algorithms for NP-hard problems : A survey'. Samen vormen ze een unieke vingerafdruk.

Citeer dit