Dureza típica de la descomposición de los árboles

12

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.

  1. ¿Se sabe algo sobre la dureza de la descomposición del árbol de una instancia "típica" de alguna clase de gráficos?
  2. ¿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?
Yaroslav Bulatov
fuente
deberías agregarlo como respuesta: incluso hay una insignia para aceptar tu propia respuesta
Suresh Venkat

Respuestas:

7

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δnnϵϵ=δ1δ+1δ=3n

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

Yaroslav Bulatov
fuente