La théorie des mineurs de graphes introduite par Seymour et Robertson dans les années 1980 a permis de formaliser la recherche en théorie des graphes de façon très significative. Un mineur d'un graphe est un graphe obtenu à partir du graphe d'origine après une suite des deux opérations suivantes: l'élimination d'arêtes et la contraction d'arêtes. Un problème important consiste à la reconnaissance de mineur d'un graphe. Cette question est importante car elle conditionne l'efficacité de certains algorithmes de reconnaissances de classes de graphes qui ne doivent pas contenir certains graphes comme mineur (l'exemple le plus simple et bien résolu est la recherche d'un graphe complet à 5 sommets ou d'un graphe biparti complet à 6 sommets (K3,3) donnant un critère de non-planarité d'un graphe)
Le but de ce stage est d'analyser dans le détail un article qui présente une méthode de recherche d'un mineur particulier dans un graphe. Une implémentation eput éventuellement être envisagée en fonction de l'avancée du problème. Tous les problèmes seront abordés de manière progressive.
Cormen, Leiserson, Rivest et Stein, "Introduction à l'Algorithmique", Dunod.
I. Hicks, "Branch Decomposition and Minor Containment", Networks, Vol 43(1) pp 1--9, 2004.