Exposé de P. Pesneau dans le cadre de la journée IREM

Si on représente un réseau de télécommunications sous la forme d'un graphe, une condition de fiabilité consiste à imposer l'existence de deux chemins arête-disjoints entre chaque paire de sommets du graphe. Ainsi, si un lien de communication vient à tomber en panne, il existe toujours un second chemin pour transmettre l'information. En associant un coût de construction à chaque lien qu'il serait possible d'établir dans le réseau, le problème qui se pose est de chercher un sous-graphe de coût minimum vérifiant la condition de fiabilité ci-dessus. Nous pourrons ajouter des conditions supplémentaires afin d'assurer une qualité de service minimum en cas de panne.

Les approches polyédrales permettent la résolution de ce type de problème (nommé programme linéaire en nombres entiers). Nous en ferons une présentation puis l'illustrerons avec l'exemple précédent.

Page des journées IREM

https://math-interactions.u-bordeaux.fr/Centres-de-ressources/IREM/Journees-IREM

Mots clés
IREM




Début de la vidéo
Cochez la case pour indiquer le début de lecture souhaité.

Table des scores

C'est la première fois que vous regardez cette vidéo.