10441 Abstracts Collection – Exact Complexity of NP-hard Problems

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



PDF
Thumbnail PDF

File

DagSemProc.10441.1.pdf
  • Filesize: 0.57 MB
  • 22 pages

Document Identifiers

Author Details

Thore Husfeldt
Dieter Kratsch
Ramamohan Paturi
Gregory B. Sorkin

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

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)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail