Dureza típica da decomposição de árvores?

12

Na pior das hipóteses, a decomposição de árvores é difícil, mas o método ganancioso parece quase ideal em pequenas redes da vida real.

  1. Existe algo conhecido sobre a dureza da decomposição de árvores em uma instância "típica" de alguma classe de gráficos?
  2. Existe exemplo de uma família de gráficos em que os métodos gananciosos de decomposição de árvores se saem mal?
Yaroslav Bulatov
fonte
você deve adicioná-lo como uma resposta: não há sequer um emblema para aceitar a sua própria resposta
Suresh Venkat

Respostas:

7

Acabei de encontrar um artigo relevante - Kloks / Boedlander "Apenas alguns gráficos delimitam a largura das árvores". Eles mostram que quase todos os gráficos com vértices e δ n arestas têm largura de árvore na ordem de n ϵ , ϵ = δ - 1nδnnϵϵ=δ1δ+1δ=3n

Portanto, mesmo que o método ganancioso encontre a melhor decomposição para todos os gráficos, o algoritmo resultante ainda seria intratávelmente lento para gráficos típicos

Yaroslav Bulatov
fonte