Back to Search Start Over

Contraction Bidimensionality: the Accurate Picture

Authors :
Fomin, Fedor V.
Golovach, Petr
Thilikos, Dimitrios M.
Publication Year :
2010
Publisher :
Schloss Dagstuhl - Leibniz-Zentrum f��r Informatik, 2010.

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.

Details

Language :
English
Database :
OpenAIRE
Accession number :
edsair.doi...........3a6003022b424bdef63f35dceee367b5
Full Text :
https://doi.org/10.4230/dagsemproc.09511.5