10441 Abstracts Collection – Exact Complexity of NP-hard Problems

Husfeldt, Thore; Kratsch, Dieter; Paturi, Ramamohan; Sorkin, Gregory B.

doi:10.4230/DagSemProc.10441.1

Document

10441 Abstracts Collection – Exact Complexity of NP-hard Problems

Authors Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, Gregory B. Sorkin

Part of: Volume: Dagstuhl Seminar Proceedings, Volume 10441
Part of: Series: Dagstuhl Seminar Proceedings (DagSemProc)
License: Creative Commons Attribution 4.0 International license
Publication Date: 2011-01-27

PDF

File

PDF

DagSemProc.10441.1.pdf

Filesize: 0.57 MB
22 pages

Document Identifiers

DOI: 10.4230/DagSemProc.10441.1
URN: urn:nbn:de:0030-drops-29363

Subject Classification

Keywords

Complexity
Algorithms
NP-hard Problems
Exponential Time
SAT
Graphs

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get 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

Author Details

Thore Husfeldt

Dieter Kratsch

Ramamohan Paturi

Gregory B. Sorkin

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail