Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451)

Kratsch, Stefan; Lokshtanov, Daniel; Marx, Dániel; Rossmanith, Peter

doi:10.4230/DagRep.4.11.1

Document

Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451)

Authors Stefan Kratsch, Daniel Lokshtanov, Dániel Marx, Peter Rossmanith and all authors of the abstracts in this report

Part of: Issue: Dagstuhl Reports, Volume 4, Issue 11
Part of: Volume: Dagstuhl Reports, Volume 4
Part of: Journal: Dagstuhl Reports (DagRep)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2015-03-20

PDF

File

PDF

DagRep.4.11.1.pdf

Filesize: 1.32 MB
21 pages

Document Identifiers

DOI: 10.4230/DagRep.4.11.1
URN: urn:nbn:de:0030-drops-49677

Subject Classification

Keywords

Algorithms
parameterized complexity
kernels
width measures
exponential time hypothesis
lower bounds

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

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

Author Details

Stefan Kratsch

Daniel Lokshtanov

Dániel Marx

Peter Rossmanith

and all authors of the abstracts in this report

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