Sujet-These-BDI

Chemins  dans  des  graphes  avec  transitions  interdites  
Proposition  de  thèse  financée   BDI -­‐CNRS  
 
ntsEncarad  :  
Mamadou  Kanté        (MdC  LIMOS,  mamadou.kante@isima.fr ),    
Christia  Laforest  (Prof.  LIMOS,   laforest@isima.fr ),    
Annegret  Wagler      (MdC  LIMOS,  chaire  CNRS/UBPw,  agler@isima.fr ).    
 
Lieu  des  travau  x:  laboratoire  LIMOS/CNRS  ( http://limos.isima.fr/ ),  Université  Baise  
Pascal  (p://w.univ -­‐bpclermont.fr)/,  Clermont  Ferrand,  Auverg  ne.
 
Financements  des  travaux  de  recherch  e:  CNRS  et  région  Auvergn  e.  
 
Mots  clés  :  graphes,  optimisation  discrète,  atlhgomirique,  approximation  polynomiale,  
algorithmique  online,  heuristiqu  e.  
Motivations  pratiques  du  sujet.    
Les  problèmes  liés  au  transport  ou  à  la  circulation  de  biens,  de  marchandises  ou  
d'information  sont  cruciaux.  Il  faut  organiser  les  réseaux  de  n  dotidisetr  teiblleu  façn  o
que  "l'écoulement"/le  mouvement  des  éléments  à  transporter  se  passe  le  mieux  
possible,  potentiellement  sur  les  "routes"  les  plus  co  urtes.  
 
Lorsque  e  résea  est  doné,  savoir    y  a  e  e  enre  deu  s  et/  ver  
une  plus   courte  route  est  un  problème  connu  qui  peut  facilement  être  résolu  avec  des  
algorithmes  classiques  de  parcours  de  graphes  (enseignés  en  Licence  informatique),  
même  si  les  tronçons  sont  pondérés  .  
 
Cependa,  en  rae,  des  conraes  euven  venir  s’a uter.  Le  sujet  de  cette  thèse  
porte  sur  la  variante  suivante  :  en  certains  points  du  réseau,  il  peut  être  impossible  (ou  
erdit)  de  poursuivre  une  route  vers  tel  point  voisin  si,  au  pas  d'ava,  on  est  arrivé  par  
telle  ou  telle  arteê /rue/acc.  sè  
 
Ceci  eut  se  retrouver  dans  diveress  situations  pratiques  :    
 
• Dans  une  ville,  il  peut  être  interdit  de  tourner  (à  gauche  par  exemple)  à  telle  
ersection  si  on  vient  de  tele  rue.  Ces  restrictions  peuvent  s'aiquer  à  tous  les  
automobilistes  (pour  éviter  de  uper"  la  rcooute  à  ceux  qui  viennent  d’en  face")  ou  
à  certaines  catégories  d'usagers  (les  camions  par  ex  emple).  
• Les  réseaux  informatiques  connectent  souvent  plusieurs  réseaux  "privés"  entre  
eux.  On  peut  imaginer  que  les  opérateurs/gestionnaires/administrars  tde  eu
certains  réseaux  ne  veulent  pas  router  des  paquets  provenant  de  tel  réseau  (pour  
des  raisons  de  sécurité,  financières,  d'incompatibilité  technologiqu  e,  etc.).  
• On  retrouve  ce  type  de  problématique  dans  un  projet  de  régularisation  de  
maillages  (travaux  d’un  encadrant  avec  le  CEA,  difficiles  à  dé  crire  ici).  
 
ppl l int
p
nt int
oj t p int t iqut p tn
rout ou ointp x t rout nu s'il n u l
ww tht
l
nDescription  du  sujet  et  travail  atendu.    
Le  problème  informatique  peut  être  décrit  comme  la  donnée  d'un  graphe  G  (qui  
représente  le  réseau)  et,    pour  chaque  sommet  u  de  G,  d'un  ensemble  de  ions  transit
erdites.    
 
Certains  résultats  connus  montrent  que  le  problème  (très  simple  sans  ces  restrictions  
dues  aux  transitions  interdites)  de  savoir  s'il  existe  une  route  entre  deux  sommets  
donnés  est  difficile  (NP -­‐complet).    
 
Le  (la)  cadida(e)  devra  :  faire  un  éta  de  l’a  précis  des  avancées  récentes  sur  ce  sujet.  
Quels  sont  les  cas  connus  faciles  (polynomiaux)  et  d  ?  ifAlficgoilreisthme  exact  
(exponentiel)  dans  le  cas  généra  ?  
Ensuite  il/elle  devra  travailler  les  problématiques  suivantes  (en  partie  en  totalité).  ou  
• Etudier  des  cas  particulier  ds e  transitions  interdites  et  de  graphes.    
• Proposer  des  algorithmes  pour  trouver  des  chemins  dans  ces  divers  sous  cas.  Il  
devra  s’efforcer  de  quantifier  analytiquement  la  longueur  et/ou  le  nombre  de  ces  
chemins  (apr  rapport  à  l’optimal,  ce  qui  conduit  à  proposer  un  algorithme  exact  
ou  un  algorithme  d’approximation).  
• Les  graphes  pouvant  être  très  gros/volumineux,  il  faudra  donc  proposer  des  
méthodes  «  egèrlé s  »  (éventuellement  en  dégradant,  de  manière  maitrisée,  l  es
résultats  retournés  pour  avoir  des  méthodes  plus  rapides).  Par  exemple  un  
algorithme  probabiliste  à  faible  complexité  qui  construirait,  avec  forte  
probabilité,  un  chemin  lorsqu’il  en  exist  e  un.  
• Des  contraintes  dynamiquesd  evront  aussi  être  prises  en  cteosmp  (par  exemple  
une  transition  qui  était  interdite  devient  autorisée).  Comment  mettre  à  jour  les  
es  sas    avoir    recacuer  lorsque  ces  changements  sont  limités  ?  
• Das  es  cas  rès  difficiles,  e  cadida  devra  oser  des  heues  et  devra  
s’efforcer  de  montrer  (de  manière  éventuellement  expérimentale)  la  qualité  des  
as  retés.    
Applications  concrètes  potentielles  des  résultats  des  travaux.    
Les  résultats  pourraient  potentiellement  être  utilisés  pou  r  :  
• Trouver  des  routes  lorsque   c'est  possible  ou  dire  que  c'est  impossible/diff  icile.
• Aider  les  concepteurs  de  réseaux  à  éviter  de  construire  des  réseaux  dans  lesquels  
 exe  des  couples  de  points  qui  ne  sont  pas  connectabes.    
• Aider  les  gestionnaire