License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-25009
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2500/
Go to the corresponding Portal |
Fomin, Fedor V. ;
Golovach, Petr ;
Thilikos, Dimitrios M.
Contraction Bidimensionality: the Accurate Picture
Abstract
We provide new combinatorial theorems on the structure of graphs that are contained as contractions in graphs of large treewidth. As a consequence of our combinatorial results we unify and significantly simplify contraction bidimensionality theory -- the meta algorithmic framework to design efficient parameterized and approximation algorithms for contraction closed parameters.
BibTeX - Entry
@InProceedings{fomin_et_al:DSP:2010:2500,
author = {Fedor V. Fomin and Petr Golovach and Dimitrios M. Thilikos},
title = {Contraction Bidimensionality: the Accurate Picture},
booktitle = {Parameterized complexity and approximation algorithms},
year = {2010},
editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D{\'a}niel Marx},
number = {09511},
series = {Dagstuhl Seminar Proceedings},
ISSN = {1862-4405},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2500},
annote = {Keywords: Paramerterized Algorithms, Bidimensionality, Graph Minors}
}
Keywords: |
|
Paramerterized Algorithms, Bidimensionality, Graph Minors |
Seminar: |
|
09511 - Parameterized complexity and approximation algorithms |
Issue Date: |
|
2010 |
Date of publication: |
|
02.03.2010 |