|
|||||
|
|
Contraction obstructions for treewidth |
|
| Authors: | Fedor V. Fomin Petr Golovach Dimitrios M. Thilikos |
| Affiliation: | a Department of Informatics, University of Bergen, N-5020 Bergen, Norway b School of Engineering and Computing Sciences, Durham University, United Kingdom c Department of Mathematics, National & Kapodistrian University of Athens, Panepistimioupolis, GR-15784, Athens, Greece |
| Abstract: | We provide two parameterized graphs Γk, Πk with the following property: for every positive integer k, there is a constant ck such that every graph G with treewidth at least ck, contains one of Kk, Γk, Πk as a contraction, where Kk is a complete graph on k vertices. These three parameterized graphs can be seen as “obstruction patterns” for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences. |
| Keywords: | Graph minor Graph contraction Bidimensionality Treewidth |
| 本文献已被 ScienceDirect 等数据库收录！ | |