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 ce stage 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 pendant ce stage (éventuellement en thèse) :

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 : Il est clair qu'un tel sujet peut déboucher sur un sujet de thèse sur des problèmes connexes, notamment le/la candidat(e) motivé(e) pourra s'insérer éventuellement dans deux projets du LaBRI soutenu 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.