Contraction Bidimensionality: the Accurate Picture

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



PDF
Thumbnail PDF

File

DagSemProc.09511.5.pdf
  • Filesize: 196 kB
  • 12 pages

Document Identifiers

Author Details

Fedor V. Fomin
Petr Golovach
Dimitrios M. Thilikos

Cite AsGet BibTex

Fedor V. Fomin, Petr Golovach, and Dimitrios M. Thilikos. Contraction Bidimensionality: the Accurate Picture. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
https://doi.org/10.4230/DagSemProc.09511.5

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.
Keywords
  • Paramerterized Algorithms
  • Bidimensionality
  • Graph Minors

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail