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.FSTTCS.2016.5
URN: urn:nbn:de:0030-drops-68903
URL: http://dagstuhl.sunsite.rwth-aachen.de/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
Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 10.12.2016

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