skip to main content

Contraction obstructions for treewidth

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

Journal of Combinatorial Theory, Series B, 2011, Vol.101(5), pp.302-314 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por
  • Título:
    Contraction obstructions for treewidth
  • Autor: Fomin, Fedor V. ; Golovach, Petr ; Thilikos, Dimitrios M.
  • Assuntos: Graph Minor ; Graph Contraction ; Bidimensionality ; Treewidth
  • É parte de: Journal of Combinatorial Theory, Series B, 2011, Vol.101(5), pp.302-314
  • Descrição: We provide two parameterized graphs Γ k , Π k with the following property: for every positive integer k, there is a constant c k such that every graph G with treewidth at least c k , contains one of K k , Γ k , Π k as a contraction, where K k 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.
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.