DagRep.4.11.1.pdf
- Filesize: 1.32 MB
- 21 pages
Document
Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451)
Authors and all authors of the abstracts in this report
-
Part of:
Issue:
Dagstuhl Reports, Volume 4, Issue 11
Volume: Dagstuhl Reports, Volume 4
Journal: Dagstuhl Reports (DagRep) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-03-20
Cite As Get BibTex
Stefan Kratsch, Daniel Lokshtanov, Dániel Marx, and Peter Rossmanith. Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451). In Dagstuhl Reports, Volume 4, Issue 11, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/DagRep.4.11.1
Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14451 "Optimality and tight results in parameterized complexity". Over the last two decades parameterized complexity has become one of the main tools for handling intractable problems. Recently, tools have been developed not only to classify problems, but also to make statements about how close an algorithm is to being optimal with respect to running time. The focus of this seminar is to highlight and discuss recent, relevant results within this optimality framework and discover fruitful research directions. The report contains the abstracts of the results presented at the seminar, as well as a collection of open problems stated at the seminar.
Subject Classification
Keywords
- Algorithms
- parameterized complexity
- kernels
- width measures
- exponential time hypothesis
- lower bounds
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads