License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-29363
URL: http://drops.dagstuhl.de/opus/volltexte/2011/2936/
Husfeldt, Thore ; Kratsch, Dieter ; Paturi, Ramamohan ; Sorkin, Gregory B.

10441 Abstracts Collection -- Exact Complexity of NP-hard Problems

pdf-format:
Dokument 1.pdf (586 KB)

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.

BibTeX - Entry

@InProceedings{husfeldt_et_al:DSP:2011:2936,
  author =	{Thore Husfeldt and Dieter Kratsch and Ramamohan Paturi and Gregory B. Sorkin},
  title =	{{10441 Abstracts Collection -- Exact Complexity of NP-hard Problems}},
  booktitle =	{Exact Complexity of NP-hard Problems},
  year =	{2011},
  editor =	{Thore Husfeldt and Dieter Kratsch and Ramamohan Paturi and Gregory B. Sorkin},
  number =	{10441},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/2936},
  annote =	{Keywords: Complexity, Algorithms, NP-hard Problems, Exponential Time, SAT, Graphs}
}

Keywords: Complexity, Algorithms, NP-hard Problems, Exponential Time, SAT, Graphs
Seminar: 10441 - Exact Complexity of NP-hard Problems
Issue date: 2011
Date of publication: 27.01.2011

DROPS-Home | Fulltext Search | Imprint Published by LZI