License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.1
URN: urn:nbn:de:0030-drops-55663
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5566/
Go to the corresponding LIPIcs Volume Portal

Thilikos, Dimitrios M.

Bidimensionality and Parameterized Algorithms (Invited Talk)

pdf-format:
4.pdf (0.6 MB)

Abstract

We provide an exposition of the main results of the theory of bidimensionality in parameterized algorithm design. This theory applies to graph problems that are bidimensional in the sense that i) their solution value is not increasing when we take minors or contractions of the input graph and ii) their solution value for the (triangulated) (k x k)-grid graph grows as a quadratic function of k. Under certain additional conditions, mainly of logical and combinatorial nature, such problems admit subexponential parameterized algorithms and linear kernels when their inputs are restricted to certain topologically defined graph classes. We provide all formal definitions and concepts in order to present these results in a rigorous way and in their latest update.

BibTeX - Entry

@InProceedings{thilikos:LIPIcs:2015:5566,
  author =	{Dimitrios M. Thilikos},
  title =	{{Bidimensionality and Parameterized Algorithms (Invited Talk)}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{1--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5566},
  URN =		{urn:nbn:de:0030-drops-55663},
  doi =		{10.4230/LIPIcs.IPEC.2015.1},
  annote =	{Keywords: Parameterized algorithms, Subexponential FPT-algorithms, Kernelization, Linear kenrels, Bidimensionality, Graph Minors}
}

Keywords: Parameterized algorithms, Subexponential FPT-algorithms, Kernelization, Linear kenrels, Bidimensionality, Graph Minors
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

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