DagSemProc.09511.5.pdf
- Filesize: 196 kB
- 12 pages
Document
Contraction Bidimensionality: the Accurate Picture
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 9511
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2010-03-02
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
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)
0PDF Downloads