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  oque  "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 ...