Ce cours s’intéresse aux graphes en tant qu’outil de modélisation pour la recherche opérationnelle.
Les détails se trouvent sur la page du module.
* * * * * *
Les problèmes de graphes, pertinents pour les applications, que nous étudierons, sont :
- Parcours de graphes
- Algorithmes de recherche (en profondeur / largeur) Recherche « informée » (A*)
- Coloration, en particulier pour des classes spécifiques (par ex.: graphes planaires)
- Couverture / domination
- Cheminements / flots
- Connexité / coupes / clusterisation, omposants fortement connexes
- Décomposition de graphes
- Graphes et la logique MSO
Pour les problèmes mentionnés, nous étudions des algorithmes génériques et des spécialisations efficaces, et nous étudions leur complexité. Nous nous intéressons surtout à des algorithmes à paramètre fixé qui permettent des solutions efficaces à des problèmes « difficiles ».
Les problèmes seront discutés en relation avec les applications suivantes :
- transport, affectation de ressources
- allocation de fréquences
- détection de défaillances
- tournées de véhicules
- emplois du temps / plannings
- clusterisation / réseaux sociaux
- réseaux de distribution
La bibliographie du cours est la suivante :
- J. H. van Lint, R. M. Wilson, A course in combinatorics, Cambridge University Press
- R. Diestel, Graph Theory, Springer
- A. Bondy, U. S. R. Murty, Graph Theory with Applications, Springer
- M. R. Garey, D. S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, Freeman
* * * * * *
Illustration de la méthode de déchargement pour un problème sur la bande infinie de hauteur 2.
Décomposition récursive pour l’analyse d’un problème dans les arbres orientés.
[Département d’informatique de l’UPS]