Un graphe peut être représenté par un terme utilisant des étiquettes (aux feuilles) et des opérations dépendant des étiquettes aux feuilles. Une fois qu'un graphe est représenté par un terme, on peut utiliser des automates de termes pour vérifier de nombreuses propriétés du graphe ou calculer de nombreuses informations à propos du graphe de manière élégante et uniforme.
Le problème d'obtenir à partir d'un graphe, un terme représentant ce graphe est appelé problème de la décomposition .
La largeur de clique d'un graphe (clique-width) est le nombre minimum d'étiquettes nécessaires pour obtenir un terme représentant le graphe.
Le problème de déterminer la largeur de clique est NP-complet. Il existe une réduction de ce problème au problème SAT. Mais cette technique ne permet de traiter que des petits graphes.
Cependant, on peut à l'aide d'heuristiques obtenir une décomposition d'un graphe en essayant d'économiser au maximum les étiquettes.
Le but de ce projet est d'implémenter et d'expérimenter des heuristiques de décomposition (selon la largeur de clique) de graphes.
Les graphes en entrée seront dans un format standard (Dimacs de préférence) et les termes en sortie en format texte exploitable par Autograph.
L'utilisation du langage Python pour ce travail permettrait à terme d'intégrer ce travail à la plate-forme SAGE . Mais une implémentation dans un autre langage de haut niveau est aussi acceptable.