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.
- Existe algo conhecido sobre a dureza da decomposição de árvores em uma instância "típica" de alguma classe de gráficos?
- Existe exemplo de uma família de gráficos em que os métodos gananciosos de decomposição de árvores se saem mal?
ds.algorithms
graph-theory
graph-algorithms
treewidth
Yaroslav Bulatov
fonte
fonte
Respostas:
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 δn nϵ ϵ=δ−1δ+1 δ=3 n−−√
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
fonte