Strategies d'encerclement non deterministes

Description

Nous définissons l'encerclement non-déterministe dans les graphes. Nous montrons comment ce nouvel outil peut être utilisé pour la conception d'algorithmes et pour l'analyse combinatoire de la largeur linéaire (pathwidth) comme de la largeur arborescente (treewidth) des graphes. Nous prouvons l'équivalence entre cette approche sous forme de ``jeu'' (graph searching) et la décomposition arborescente $q$-branchée d'un graphe. Cette décomposition peut être interprétée comme une version paramétrée des décompositions arborescente et linéaire qui sont deux cas extrêmes de la décomposition arborescente $q$-branchée. L'équivalence entre l'encerclement non-déterministe et la décomposition arborescente $q$-branchée nous permet de proposer un algorithme exact (en temps exponentiel) pour calculer la largeur arborescente $q$-branchée pour tout $q \geq 0$. Cet algorithme est donc valide à la fois pour la largeur linéaire et pour la largeur arborescente. Notre algorithme est aussi rapide que le meilleur algorithme connu pour la largeur linéaire.

Abstract

National audience

Additional details