La descomposición de los árboles es difícil en el peor de los casos, pero el método codicioso parece ser casi óptimo en pequeñas redes de la vida real.
- ¿Se sabe algo sobre la dureza de la descomposición del árbol de una instancia "típica" de alguna clase de gráficos?
- ¿Hay algún ejemplo de una familia de gráficos en los que los métodos ambiciosos para la descomposición de los árboles no funcionen bien?
ds.algorithms
graph-theory
graph-algorithms
treewidth
Yaroslav Bulatov
fuente
fuente
Respuestas:
Acabo de encontrar un artículo relevante: Kloks / Boedlander "Sólo unos pocos gráficos tienen el ancho del árbol acotado". Muestran que casi todos los gráficos con vértices y bordes tienen un ancho de árbol del orden de , . Por ejemplo, significa que el ancho de árbol típico crece a medida quen δn nϵ ϵ=δ−1δ+1 δ=3 n−−√
Entonces, incluso si el método codicioso encontrara la mejor descomposición para todos los gráficos, el algoritmo resultante aún sería intratablemente lento para los gráficos típicos
fuente