License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagRep.4.11.1
URN: urn:nbn:de:0030-drops-49677
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4967/
Go back to Dagstuhl Reports

Kratsch, Stefan ; Lokshtanov, Daniel ; Marx, Dániel ; Rossmanith, Peter
Weitere Beteiligte (Hrsg. etc.): Stefan Kratsch and Daniel Lokshtanov and Dániel Marx and Peter Rossmanith

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

pdf-format:
dagrep_v004_i011_p001_s14451.pdf (1 MB)

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.

BibTeX - Entry

@Article{kratsch_et_al:DR:2015:4967,
  author =	{Stefan Kratsch and Daniel Lokshtanov and D{\'a}niel Marx and Peter Rossmanith},
  title =	{{Optimality and tight results in parameterized complexity (Dagstuhl Seminar 14451)}},
  pages =	{1--21},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{11},
  editor =	{Stefan Kratsch and Daniel Lokshtanov and D{\'a}niel Marx and Peter Rossmanith},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4967},
  URN =		{urn:nbn:de:0030-drops-49677},
  doi =		{10.4230/DagRep.4.11.1},
  annote =	{Keywords: Algorithms, parameterized complexity, kernels, width measures, exponential time hypothesis, lower bounds}
}

Keywords: Algorithms, parameterized complexity, kernels, width measures, exponential time hypothesis, lower bounds
Collection: Dagstuhl Reports, Volume 4, Issue 11
Issue Date: 2015
Date of publication: 20.03.2015

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