Largeur arborescente : un paramètre clé en théorie des graphes et ses applications
Cet article explore la largeur arborescente, un paramètre crucial en théorie des graphes. Définie à l'aide de décompositions arborescentes, la largeur arborescente caractérise la structure du graphe et est étroitement liée à la complexité algorithmique. L'article explore plusieurs définitions équivalentes de la largeur arborescente, ses propriétés structurelles et ses méthodes de calcul. Il détaille ensuite ses vastes applications en algèbre linéaire numérique creuse, inférence bayésienne, théorie des jeux, topologie de basse dimension, science des réseaux et géométrie algébrique. L'auteur discute également des progrès réalisés sur les paramètres de largeur connexes et de la manière dont la largeur arborescente peut améliorer l'efficacité des algorithmes de graphes.