Introdução suave aos aspectos algorítmicos da profundidade da árvore

13

A largura da árvore e a largura do caminho são parâmetros populares, medindo a proximidade de um gráfico a uma árvore ou um caminho, respectivamente. De fato, parece que a largura da árvore é tão popular que é apresentada em muitos artigos, livros e notas de aula que dão (mesmo que muito gentil) introduções aos aspectos algorítmicos da largura da árvore (veja, por exemplo, o livro de Downey & Fellows). Normalmente, esses recursos explicam como algum problema NP-difícil (por exemplo, conjunto independente) é resolvido em tempo polinomial por meio de programação dinâmica em uma decomposição em árvore.

No entanto, às vezes é o caso de um problema gráfico permanecer NP-completo para os gráficos de largura de árvore e largura de caminho limitados. Porém, esses resultados de dureza não significam dureza para a profundidade limitada da árvore , que mede informalmente a proximidade de uma estrela.

Parece justo dizer que a profundidade das árvores não é tão conhecida como a largura das árvores. Para alguém que deseja aprender mais sobre a parametrização de algoritmos por profundidade de árvore, existem (de maneira semelhante à largura da árvore) alguns recursos interessantes disponíveis para aprender como esses algoritmos talvez normalmente funcionem?

Juho
fonte

Respostas:

10

Meu recurso favorito para esse assunto é o livro Sparsity, de Jaroslav Nešetřil e Patrice Ossona de Mendez. Possui bastante material especificamente sobre a profundidade da árvore, incluindo aspectos algorítmicos. E para uma introdução mais breve e rápida, há sempre o artigo da Wikipedia .

David Eppstein
fonte
@Juho Além disso, o capítulo 6 do livro Graph Colourings está no ranking de vértices (também chamado de coloração ordenada). Treedepth é o mesmo que o número cromático dessa variante de coloração. O capítulo do livro descreve algoritmos simples (por exemplo, em árvores).
Cyriac Antony