Sujet : Étude des graphes k-chemin séparables Responsable : Cyril Gavoille Téléphone : 05.40.00.88.12 e-mail : gavoille@labri.fr Equipe : Combinatoire et Algorithmique Thème : Graphes & Applications Présentation du sujet : Le paradigme "diviser-pour-reigner" est une approche classique employée pour résoudre de nombreux problèmes algorithmes sur les graphes. Il sagit de décomposer le graphe en morceaux plus petits, de résoudre le problème sur les morceaux puis de les recoller pour en déduire la solution du graphe en entier. La décomposition s'effectue en enlevant une partie du graphe, partie appelée séparateur. La nature même du séparateur jour un rôle fondamentale dans cette approche. Il a été montré dans [T01] et [AG06] que les graphes "k-chemin séparables" sont particulièrement bien adaptés pour les problèmes faisant intervenir les distances ou l'approximation de distances dans les graphes, comme la construction de tables de routage, d'oracle de distance, ou l'étude de l'effet "petit monde" dans les graphes. Grosso modo les graphes k-chemin séparables sont les graphes qui peuvent être coupé en deux par un séparateur composé de k plus courts chemins. Généralisant les graphes de largeur arborescente k, les graphes k-chemin sépérables contiennent les familles de graphes closes par mineur, des familles importantes contenant par exemple les graphes planaires. Dans cette thèse il s'agira d'étudier les aspects algorithmiques et structurels des graphes k-chemin séparables. Voici quelques exemple de questions qui pourront être abordées : * Peut-on calculer efficacement la décomposition d'un graphe 1-séparable ? * Existe-t-il un graphe planaire qui n'est pas 2-chemin séparable ? * Peut-on coder efficacement en mémoire les graphes k-chemin séparables ? * Que peut-on dire de la représentation en page (pagenumber [Yan89]) des graphes k-chemin séparables ? * Que peut-on dire du nombre chromatique des graphes k-chemin séparables ? * Peut-on employer des méthodes de programmation dynamique, comme pour la décomposition arborescentes, pour résoudre certains problèmes (et lesquels ?) sur les graphes k-chemin séparables ? * etc. Mot-clés : algorithmes, théorie des graphes Commentaires : le/la candidat(e) s'insérera dans deux projets du LaBRI soutenus nationalement par l'ANR : le projet "ALADIN" (apsects algorithmiques des réseaux) et le projet "GRAAL" (décomposition de graphes). Références : [AG06] Ittai Abraham, and Cyril Gavoille. Object Location Using Path Separators. 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM Press, pp. 188-197, jul. 2006. [T01] Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM, 51(6):993-1024, 2004. [Yan89] Mihalis Yannakakis. Embedding Planar Graphs in Four Pages. Journal of Computer and System Sciences, 38(1):188-197, 1989.