Contraction Bidimensionality: The Accurate Picture

Fedor V. Fomin, Petr Golovach, Dimitrios M. Thilikos

Research output: Contribution to journalConference articlepeer-review

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.

Original languageEnglish (US)
JournalDagstuhl Seminar Proceedings
Volume9511
StatePublished - 2010
EventParameterized Complexity and Approximation Algorithms 2009 - Wadern, Germany
Duration: Dec 13 2009Dec 17 2009

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'Contraction Bidimensionality: The Accurate Picture'. Together they form a unique fingerprint.

Cite this