License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.10441.1
URN: urn:nbn:de:0030-drops-29363
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/2936/
Go to the corresponding Portal

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

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

pdf-format:
10441DagstuhlSeminarReportNov2010.2936.pdf (0.6 MB)

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:DagSemProc.10441.1,
  author =	{Husfeldt, Thore and Kratsch, Dieter and Paturi, Ramamohan and Sorkin, Gregory B.},
  title =	{{10441 Abstracts Collection – Exact Complexity of NP-hard Problems}},
  booktitle =	{Exact Complexity of NP-hard Problems},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10441},
  editor =	{Thore Husfeldt and Dieter Kratsch and Ramamohan Paturi and Gregory B. Sorkin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2011/2936},
  URN =		{urn:nbn:de:0030-drops-29363},
  doi =		{10.4230/DagSemProc.10441.1},
  annote =	{Keywords: Complexity, Algorithms, NP-hard Problems, Exponential Time, SAT, Graphs}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI