Sujet : Structure de données distribuées pour le calcul de distance dans des graphes presque planaires

Responsable : Cyril Gavoille
Contact : gavoille@labri.fr
Équipe : Combinatoire et Algorithmique
Thème : Algorithmique Distribuée / Graphes et Optimisation
Type : stage Master Informatique
Durée : 5 mois en 2019
Lieu : LaBRI
Financement : en attente
Mot-clés : algorithmes de graphes, structures de données distribués, calcul de distance, graphes $k$-planaires

Présentation du sujet :

Le problème du calcul de distance ou de plus courts chemins dans un graphe, a priori valué, est un problème algorithmique classique de la théorie des graphes. Les algorithmes de calcul de courts chemins apparaissent dans très nombreux contextes, allant de la navigation de véhicules aux heuristiques utilisées en intelligence artificielle pour la recherche de solutions à des problèmes on ne peut plus variés.

On envisage ici le calcul d'une structure de données pré-calculée une fois pour toute pour le graphe d’entrée afin de pouvoir répondre le plus efficacement possible à des requêtes de distance (exacte ou approchée). De nombreuses solutions utilisent une structure de données distribuées sur les sommets à base d’étiquettes, citons par exemple [DGSW14, Thorup04, AG06]. Plus précisément, il s'agit de concevoir un schéma d'étiquetage, composé d'un encodeur (pour l'étiquetage des sommets) et un décodeur (pour le calcul de la requête). Le schéma doit être construit de sorte qu'on puisse, pour tout graphe $G$ d'une famille donnée, et toute paire de sommets $u,v$ de $G$, décoder la distance entre $u$ et $v$ sur la seule base des deux étiquettes associées aux sommets par l'encodeur. L’objectif principal est de minimiser la taille des étiquettes afin de diminuer le temps de réponse.

On se limitera dans ce stage au cas des graphes "presque" planaires représentatifs de nombreuses situations pratiques comme les réseaux routiers. On considèrera plus précisément les graphes $k$-planaires, c'est-à-dire les graphes possédant un plongement dans le plan tel qu'aucune arête ne coupe plus de $k$ autres arêtes.

Ce sujet se rattache à un domaine de recherche novateur, ayant de nombreuses extensions (soit en terme de famille de graphes, soit en terme de requêtes comme le routage par exemple) 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]

[AG06] Ittai Abraham and Cyril Gavoille. Object Location Using Path Separators. In 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 188-197. ACM Press, July 2006.

[DGSW14] Daniel Delling, Andrew V. Goldberg, Ruslan Savchenko and Renato Foncesa, Werneck. Hub Labels: Theory and Practice. In 13th International Symposium on Experimental Algorithms (SEA), pages 259-270. Volume 8504 of LNCS, Springer, June 2014.

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