Exact algorithms for NP-hard problems: A survey

Gerhard Woeginger

doi:10.1007/3-540-36478-1_17

Exact algorithms for NP-hard problems: A survey

Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

434 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 language	English
Title of host publication	Combinatorial Optimization -- Eureka, you shrink!
Subtitle of host publication	Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5–9, 2001 Revised Papers
Editors	M. Junger, G. Reinelt, G. Rinaldi
Publisher	Springer
Pages	185-207
ISBN (Print)	3-540-00580-3
DOIs	https://doi.org/10.1007/3-540-36478-1_17
Publication status	Published - 2003
Event	Jack Edmonds 5th International Workshop 2001 - Aussois, France Duration: 5 Mar 2001 → 9 Mar 2001 Conference number: 5

Publication series

Name	Lecture notes in computer science
Volume	2570
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	Jack Edmonds 5th International Workshop 2001
Country/Territory	France
City	Aussois
Period	5/03/01 → 9/03/01

Keywords

METIS-213358

Access to Document

10.1007/3-540-36478-1_17

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

@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!",

note = "Jack Edmonds 5th International Workshop 2001 ; Conference date: 05-03-2001 Through 09-03-2001",

}

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 proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Woeginger, Gerhard

N1 - Conference code: 5

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

T2 - Jack Edmonds 5th International Workshop 2001

Y2 - 5 March 2001 through 9 March 2001

ER -

Exact algorithms for NP-hard problems: A survey

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this