Introduction en douceur aux aspects algorithmiques de la profondeur des arbres

13

La largeur d'arbre et la largeur de chemin sont des paramètres populaires, mesurant la proximité d'un graphique avec un arbre ou un chemin, respectivement. En effet, il semble que la largeur d'arbre soit si populaire qu'elle figure dans de nombreux articles, livres et notes de cours qui donnent (même très doucement) des introductions aux aspects algorithmiques de la largeur d'arbre (voir par exemple le livre Downey & Fellows). Généralement, ces ressources expliquent comment un problème NP-difficile (par exemple un ensemble indépendant) est résolu en temps polynomial grâce à une programmation dynamique sur une décomposition d'arbre.

Cependant, il arrive parfois qu'un problème de graphe reste NP-complet pour les graphes à largeur d'arbre bornée et à largeur de chemin borné. Mais de tels résultats de dureté n'impliquent pas la dureté pour la profondeur d'arbre bornée , qui mesure officieusement la proximité d'une étoile.

Il semble juste de dire que la profondeur de l'arbre n'est pas aussi largement connue que la largeur de l'arbre. Pour quelqu'un qui souhaite en savoir plus sur les algorithmes de paramétrage par profondeur d'arbre, existe-t-il (de la même manière que la largeur d'arbre) de belles ressources disponibles pour apprendre comment ces algorithmes fonctionnent généralement?

Juho
la source

Réponses:

10

Ma ressource préférée pour ce sujet est le livre Sparsity de Jaroslav Nešetřil et Patrice Ossona de Mendez. Il contient un peu de matériel spécifiquement sur la profondeur des arbres, y compris les aspects algorithmiques. Et pour une introduction plus brève et rapide, il y a toujours l'article Wikipedia .

David Eppstein
la source
@Juho En outre, le chapitre 6 du livre Graph Colorings est sur le classement des sommets (également appelé coloration ordonnée). La profondeur d'arbre est identique au nombre chromatique de cette variante de coloration. Le chapitre du livre décrit des algorithmes simples (par exemple, sur les arbres).
Cyriac Antony