License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.5
URN: urn:nbn:de:0030-drops-68903
URL: http://drops.dagstuhl.de/opus/volltexte/2016/6890/
Go to the corresponding LIPIcs Volume Portal


Fomin, Fedor V.

Graph Decompositions and Algorithms (Invited Talk)

pdf-format:
LIPIcs-FSTTCS-2016-5.pdf (0.2 MB)


Abstract

We overview the recent progress in solving intractable optimization problems on planar graphs as well as other classes of sparse graphs. In particular, we discuss how tools from Graph Minors theory can be used to obtain: * subexponential parameterized algorithms * approximation algorithms, and * preprocessing and kernelization algorithms on these classes of graphs.

BibTeX - Entry

@InProceedings{fomin:LIPIcs:2016:6890,
  author =	{Fedor V. Fomin},
  title =	{{Graph Decompositions and Algorithms (Invited Talk)}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{5:1--5:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6890},
  URN =		{urn:nbn:de:0030-drops-68903},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.5},
  annote =	{Keywords: Algorithms, logic, graph minor}
}

Keywords: Algorithms, logic, graph minor
Seminar: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 08.12.2016


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