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 language | English (US) |
---|---|
Journal | Dagstuhl Seminar Proceedings |
Volume | 9511 |
State | Published - 2010 |
Event | Parameterized Complexity and Approximation Algorithms 2009 - Wadern, Germany Duration: Dec 13 2009 → Dec 17 2009 |
ASJC Scopus subject areas
- Software
- Hardware and Architecture
- Control and Systems Engineering