Back to Search
Start Over
Contraction obstructions for treewidth
- Source :
-
Journal of Combinatorial Theory - Series B . Sep2011, Vol. 101 Issue 5, p302-314. 13p. - Publication Year :
- 2011
-
Abstract
- Abstract: We provide two parameterized graphs , with the following property: for every positive integer k, there is a constant such that every graph G with treewidth at least , contains one of , , as a contraction, where 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. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 00958956
- Volume :
- 101
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- Journal of Combinatorial Theory - Series B
- Publication Type :
- Academic Journal
- Accession number :
- 60769206
- Full Text :
- https://doi.org/10.1016/j.jctb.2011.02.008