Exact algorithms for NP-hard problems: A survey

Gerhard Woeginger

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

310 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

Fingerprint

Exact Algorithms
NP-hard Problems
NP-complete problem
Precedence Constraints
Knapsack
Graph Coloring
Exponential time
Graph in graph theory
Travelling salesman problems
Independent Set
Open Problems
Scheduling
Bandwidth

Keywords

  • METIS-213358

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
Woeginger, Gerhard. / Exact algorithms for NP-hard problems: A survey. Combinatorial Optimization -- Eureka, you shrink!: Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5–9, 2001 Revised Papers. editor / M. Junger ; G. Reinelt ; G. Rinaldi. Springer, 2003. pp. 185-207 (Lecture notes in computer science).
@inproceedings{ac91a928a94b4cab80441b27e086ad5c,
title = "Exact algorithms for NP-hard problems: A survey",
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.",
keywords = "METIS-213358",
author = "Gerhard Woeginger",
year = "2003",
doi = "10.1007/3-540-36478-1_17",
language = "English",
isbn = "3-540-00580-3",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "185--207",
editor = "M. Junger and G. Reinelt and G. Rinaldi",
booktitle = "Combinatorial Optimization -- Eureka, you shrink!",

}

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. Lecture notes in computer science, vol. 2570, Springer, pp. 185-207, Jack Edmonds 5th International Workshop 2001, Aussois, France, 5/03/01. https://doi.org/10.1007/3-540-36478-1_17

Exact algorithms for NP-hard problems: A survey. / Woeginger, Gerhard.

Combinatorial Optimization -- Eureka, you shrink!: Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5–9, 2001 Revised Papers. ed. / M. Junger; G. Reinelt; G. Rinaldi. Springer, 2003. p. 185-207 (Lecture notes in computer science; Vol. 2570).

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

TY - GEN

T1 - Exact algorithms for NP-hard problems: A survey

AU - Woeginger, Gerhard

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.

KW - METIS-213358

U2 - 10.1007/3-540-36478-1_17

DO - 10.1007/3-540-36478-1_17

M3 - Conference contribution

SN - 3-540-00580-3

T3 - Lecture notes in computer science

SP - 185

EP - 207

BT - Combinatorial Optimization -- Eureka, you shrink!

A2 - Junger, M.

A2 - Reinelt, G.

A2 - Rinaldi, G.

PB - Springer

ER -

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