Sujet : Structures de données métriques

Responsable : Cyril Gavoille
Téléphone : 05.40.00.88.12
e-mail : gavoille@labri.fr
Site Web : http://dept-info.labri.fr/~gavoille
Equipe : Combinatoire et Algorithmique

Présentation du sujet :

Trouver le plus court chemin pour aller d'un point A à un point B est un problème d'optimisation classique. Pour éviter la dépense de temps, d'argent, ou d'autre ressource, il est souvent très rentable de produire un petit effort pour trouver le meilleur chemin. Depuis longtemps de nombreux outils ont été développés pour rendre plus efficace le routage ou la navigation, en particulier pour les réseaux routiers. Parmi eux citons les cartes routières, la numérotation des rues et des habitations, et plus récemment les services en ligne comme Mappy, Google Maps, Yahoo Maps, etc. Le degré de sophistication de ces outils est très variable, mais ils sont au final de simple structures de données représentant les caractéristiques d'un espace métrique, ici le réseaux routier. Nous utilisons le terme de "structures de données métriques" pour capturer toute représentation discrète ou approximée d'un espace métrique, le plus souvent modélisée par un graphe pondéré, permettant la résolution de requêtes spécifiques à propos de cette métrique.

Le sujet comprend l'étude du problème du calcul de distance et/ou de la route dans un graphe à l'aide de représentations (c'est-à-dire de structures de données) efficaces. L'approximation de la distance et/ou de la route permet souvent de réduire considérablement l'espace des structures de données mise en jeu. On pourra envisager d'approximer les distances à un facteur additif près, plutôt que multiplicatif. Afin de répondre à des requêtes du type "Quel est le plus court chemin du point A au point B qui évite le point C ?" on pourra aussi enrichir les structures de données pour qu'elles supportent des requêtes avec des ensembles interdits (forbidden set [CT07]). Enfin, une propriété parfois essentielle est la capacité de la structure de données à être localisée [AG06, GL07], comme les tables de routage qui doivent être locales à chaque routeur.

Ce sujet combine algorithmique et théorie des graphes, et recouvre la construction et l'optimisation des objets suivants :

oracle de distance, étiquetage de distance [DT02, DP08, AG06]
schéma de routage compact [Dom07]
squelette et sous-graphes éparses (spanners) [CLPR09, DGPV08b]
plongement de métrique, graphes universel [LM08, GL07]

Ce sujet est financé par un projet ANR "ALADDIN" (programme blanc), projet en partenariat avec le LIAFA. Il s'insère également dans l'équipe-projet INRIA Sud-Ouest "CEPAGE". Si vous êtes intéressé merci de me contacter par email en joignant:

un CV ;
une lettre de motivation ; et
les contacts de deux référents chercheurs ou enseignants-chercheurs.

Mot-clés : théorie des graphes, complexité, algorithmique et structures de données

Références :

[AG06] I. Abraham and C. Gavoille, Object location using path separators
in 25th Annual ACM Symposium on Principles of Distributed Computing (PODC)
ACM Press, July 2006, pp. 188-197.

[CT07] B. Courcelle and D. A. Twigg, Compact forbidden-set routing
in 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS)
vol. 4393 of LNCS, Springer, Feb. 2007, pp. 37-48.

[CLPR09] S. Chechik, M. Langberg, D. Peleg, and L. Roditty, Fault-tolerant spanners for general graphs
in 41st Annual ACM Symposium on Theory of Computing (STOC)
ACM Press, June 2009.

[DGPV08b] B. Derbel, C. Gavoille, D. Peleg, and L. Viennot, On the locality of distributed sparse spanner construction
in 27th Annual ACM Symposium on Principles of Distributed Computing (PODC)
ACM Press, Aug. 2008, pp. 273-282.

[Dom07] M. Dom. Compact routing
in Algorithms for Sensor and Ad Hoc Networks
vol. 4621 of LNCS, Springer, 2007, pp. 187-202.

[DP08] R. Duan and S. Pettie, Bounded-leg distance and reachibility oracles
in 19th Symposium on Discrete Algorithms (SODA)
ACM-SIAM, Jan. 2008, pp. 436-445.

[DT02] C. Demetrescu and M. Thorup, Oracles for distances avoiding a link-failure
in 13th Symposium on Discrete Algorithms (SODA)
ACM-SIAM, Jan. 2002, pp. 838-843.

[GL07] C. Gavoille and A. Labourel, Shorter implicit representation for planar graphs and bounded treewidth graphs
in 15th Annual European Symposium on Algorithms (ESA), vol. 4698 of LNCS, Springer, Oct. 2007, pp. 582--593.

[LM08] T. Leighton and A. Moitra, Some results on greedy embeddings in metric spaces
in 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS)
IEEE Computer Society Press, Oct. 2008, pp. 337-346.