DagSemProc.10441.1.pdf
- Filesize: 0.57 MB
- 22 pages
Document
10441 Abstracts Collection – Exact Complexity of NP-hard Problems
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 10441
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2011-01-27
Cite AsGet BibTex
Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, and Gregory B. Sorkin. 10441 Abstracts Collection – Exact Complexity of NP-hard Problems. In Exact Complexity of NP-hard Problems. Dagstuhl Seminar Proceedings, Volume 10441, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/DagSemProc.10441.1
https://doi.org/10.4230/DagSemProc.10441.1
Abstract
A decade before NP-completeness became the
lens through which Computer Science views computationally hard
problems, beautiful algorithms were discovered that are much better
than exhaustive search, for example
Bellman's 1962 dynamic programming treatment of the Traveling Salesman problem
and Ryser's 1963 inclusion--exclusion formula for the permanent.
Keywords
- Complexity
- Algorithms
- NP-hard Problems
- Exponential Time
- SAT
- Graphs
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads