Introducción suave a los aspectos algorítmicos de la profundidad de los árboles.

13

El ancho de árbol y el ancho de ruta son parámetros populares, que miden la cercanía de un gráfico a un árbol o una ruta, respectivamente. De hecho, parece que el ancho de árbol es tan popular que aparece en muchos documentos, libros y notas de conferencias que ofrecen (incluso muy suaves) introducciones a los aspectos algorítmicos del ancho de árbol (ver, por ejemplo, el libro de Downey & Fellows). Típicamente, estos recursos explican cómo se resuelve un problema NP-duro (por ejemplo, un conjunto independiente) en tiempo polinómico a través de la programación dinámica en la descomposición de un árbol.

Sin embargo, a veces es el caso de un problema gráfico que sigue siendo NP completo para los gráficos de ancho de árbol acotado y de ancho de ruta acotado. Pero tales resultados de dureza no implican dureza para la profundidad del árbol acotada , que mide informalmente la cercanía a una estrella.

Parece justo decir que la profundidad del árbol no es tan conocida como el ancho del árbol. Para alguien que quiera aprender más sobre los algoritmos de parametrización por profundidad de árbol, ¿existen (de manera similar al ancho de árbol) algunos recursos disponibles para aprender cómo funcionan estos algoritmos?

Juho
fuente

Respuestas:

10

Mi recurso favorito para este tema es el libro Sparsity por Jaroslav Nešetřil y Patrice Ossona de Méndez. Tiene bastante material específicamente sobre la profundidad del árbol, incluidos los aspectos algorítmicos. Y para una introducción más breve y rápida, siempre está el artículo de Wikipedia .

David Eppstein
fuente
@Juho Además, el capítulo 6 del libro Graph Colours está en la clasificación de vértices (también llamada coloración ordenada). La profundidad de árbol es igual al número cromático de esta variante de color. El capítulo del libro describe algoritmos simples (por ejemplo, en árboles).
Cyriac Antony