Sujet : Accéssibilité dans les graphes planaires orientés avec pannes

Responsable : Cyril Gavoille
Contact : gavoille@labri.fr
Équipe : Combinatoire et Algorithmique
Thème : Algorithmique Distribuée
Type : stage Master Informatique
Durée : 4 mois (février - mai 2018)
Lieu : LaBRI
Financement : oui
Mot-clés : algorithmes de graphes, calcul distribué, structures de données distribués

Présentation du sujet :

Le problème d’accessibilité (ou reachability problem) dans un graphe orienté $G$ est de savoir si, pour deux sommets $s$ et $t$ donnés, $G$ contient un chemin allant de $s$ à $t$. Le sujet de ce stage porte sur une généralisation de ce problème de base apparaissant dans de nombreux contextes en informatique, en particulier lorsque certains sommets du graphe sont défaillant. Plus précisément il s’agit de calculer une structure de données pour $G$ permettant de répondre le plus efficacement possible à la question de l’existence d’un chemin allant de $s$ à $t$ dans le graphe $G \setminus F$, c’est-à-dire le graphe $G$ dont les sommets d’un sous-ensemble $F$ donné ont été supprimés.

Bien que la solution algorithmique soit élémentaire (un simple parcours du graphe depuis le sommet source), dans de nombreuses applications on souhaite cependant répondre à de nombreuses requêtes et pour des graphes gigantesques (plusieurs millions de sommets et centaines de millions d’arcs, voir beaucoup plus pour des graphes denses). Dans ces conditions, un parcours même en temps linéaire n’est pas assez efficace pour obtenir des réponses en temps réel. Le calcul d’une structure de données précalulée une fois pour toute pour le graphe d’entrée est une solution envisagée. De nombreuses solutions comme [CHKZ03], utilisent une structure de données à base d’étiquettes, citons par exemple [CGKT09, Thorup15, Halftermeyer14] pour le cas planaire non-orienté et [HTR15] pour le cas orienté. L’objectif étant le plus souvent de minimiser la taille des étiquettes afin de diminuer le temps de réponse. On se limitera dans ce stage au cas des graphes planaires [CGKT09, Thorup04, KKS05] représentatifs de nombreuses situations pratiques comme les réseaux routiers.

Ce sujet se rattache à un domaine de recherche novateur et peut faire l'objet, selon la motivation et le travail du candidat, d'une poursuite en thèse.

Références :

[login: gavoille, pwd: bib0]

[CHKZ03] Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. Reachability and distance queries via 2-hop labels. SIAM Journal on Computing, 32(5):1338-1355, 2003.

[CGKT09] Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté, and David Andrew Twigg. Optimal labelling for connectivity checking in planar networks with obstacles. Technical Report hal-00367746, HAL, March 2009.

[Halftermeyer14] Pierre Halftermeyer. Connexité dans les réseaux et schémas d'étiquetage compact dans l'urgence. Phd thesis, Université de Bordeaux, Talence, France, September 2014. tel-01110316.

[HRT15] Jacob Holm, Eva Rotenberg, and Mikkel Thorup. Planar reachability in linear space and constant time. In 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 370-389. IEEE Computer Society Press, October 2015.

[Thorup04] Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM, 51(6):993-1024, November 2004.

[KKS05] Irit Katriel, Martin Kutz, and Martin Skutella. Reachability substitutes for planar digraphs. Technical Report MPI-I-2005-1-002, Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany, March 2005.