Notions en théories des graphes, algorithmique, structure de données, compléxité et analyse d'algorithmes (ULIN301, ULIN501,
ULIN503, UMINM112).
Controle connaissances
3
Description de l'UE :
Semestre
Code
Intitulé
Cours
TD
TP
TER
S3
UMINR316
Algorithmique combinatoire
15h
-
-
Detail du programme
Objectifs : Contenu :
Objectif
L'objectif de ce module est l'étude de propriétés combinatoires des graphes permettant la mise au point d'algorithmes efficaces.
Par exemple, quelles sont les propriétés nécessaires ou suffisantes pour qu'un problème non polynomial en général, devienne
polynomial sur une classe de graphes. Plusieurs problématiques sont ainsi abordées:
Plan
1. Familles restreintes de graphes: Présentation de quelques familles de graphes présentant des propriétés combinatoires
fortes (graphes triangulés, graphes d'intervalles, graphes planaires...)
2. Algorithmes de reconnaissance: Comment tester si un graphe appartient ou non à une famille de graphes ? Comment produire
un certificat à cette question (dans le cas positif comme négatif). Ces questions sont des problèmes de base en algorithmique
pour les graphes. Il existe quelques paradigmes permettant de les abordées efficacement: le calcul de schémas d'élimination
simpliciaux, parcours de graphes, affinage de partition. Des variantes du problème de reconnaissance sont abordés, problèmes
de complétion, sandwich problème...
3. Décomposition de graphe: L'existence d'une décomposition est souvent la clé permettant d'obtenir des algorithmes polynomiaux.
Dans ce domaine, la décomposition modulaire et ses variantes, la largeur aborescente sont des outils puissants qui interviennent
par exemple dans la reconnaissance et le théorème de caractérisation des graphes parfaits.
4. Codage de graphes: Comment représenter de manière compact un graphe. Les propriétés combinatoires de certaines familles
permettent souvent d'obtenir des caractérisations sous forme de modèles d'intersection. Ces caractérisations offrent naturellement
des codages efficaces de ces graphes. En ajoutant un peu d'information, il est parfois possible d'utiliser ces codages pour
mettre au point des algorithmes de calcul de distance, routage... de manière centralisé et/ou distribués.
5. Algorithmique pour les graphes dynamiques: De plus en plus les algorithmes doivent être résistant "aux pannes". Autrement
dit étant donnée une solution à un problème pour un graphe, il faut être capable de modifer cette solution, sans tout recalculer,
lorsqu'un changement intervient dans le graphe. Ces changements sont par exemples, l'ajout ou la suppression de sommets et/ou
d'arêtes.
