Sujet de stage de recherche - Master informatique

  • titre: Algorithmes de graphes pour les télécommunications sans-fil.
  • Responsable: Arnaud Pêcher (professeur)
  • Téléphone : 05 40 00 60 78
  • e-mail: pecher@labri.fr
  • Équipe: Combinatoire et Algorithmique
  • Thème : Graphes et applications
  • Equipe INRIA: RealOpt

Présentation du sujet :

L'objectif scientifique de ce stage est d'aborder les problématiques en télécommunications sans-fil, avec les outils des colorations de graphes et de la programmation mathématique. Les colorations de graphes sont au cœur de la modélisation de nombreux types de réseaux: dans les réseaux à multiplexage en longueur d'onde, les couleurs représentent les longueurs d'onde; dans les réseaux à tolérance de panne, les couleurs représentent les dispositifs qui partagent une même ressource à risque ...

Il s'agit d'étudier les possibilités induites par des types de colorations de graphes très récents, comme les L(p,q)-colorations par listes, et leurs applications en télécommunications. Compte tenu des applications visées, cette étude s'inscrira naturellement dans un cadre plus vaste que la théorie des graphes et devra notamment prendre en compte les méthodes issues de la programmation mathématique, dont la programmation linéaire.

Une attention toute particulière sera apportée à la conception d'algorithmes efficaces en les validant sur les jeux de tests classiques tels que ceux recensés par le site web http://fap.zib.de (dédié aux problèmes d'allocations de fréquences) par exemple.

Le stage sera effectué au sein du thème "Graphes et applications" du LaBRI (https://graphesetapplications.labri.fr/) et de l'équipe INRIA RealOpt (https://wiki.bordeaux.inria.fr/realopt/), dans le cadre du projet ANR GraTel (https://gratel.labri.fr/).