Evènement pour le groupe GT Graphes et Applications


Date 2008-03-28  14:00-15:00
TitreEmpilements et recouvrements dans les graphes 
RésuméLes problèmes d'empilements et de recouvrements, certes moins populaires que les problèmes de coloration, sont néanmoins des problèmes fondamentaux de la théorie des graphes. En particulier, on peut relier les problèmes d'empilement à une bonne partie de la théorie des codes correcteurs. De plus, la domination est un problème de recouvrement qui attire largement l'attention, comme le prouve la vaste littérature sur le sujet. Au cours de cet exposé, nous parlerons d'abord de paire-domination, une variante de la domination introduite par Haynes et Slater. Nous verrons quels sont les cas critiques pour ce paramètre, et quelles bornes l'exclusion de ces cas permet d'obtenir. Puis, nous continuerons l'étude des codes pondérés entamée par Cohen, Honkala, Lytsin et Mattson. Dans le cas parfait, un code pondéré de rayon 1 nécessite une certaine régularité qui nous permet de déterminer dans la plupart des cas l'existence ou l'inexistence de codes.  
LieuSalle 75 
OrateurPaul Dorbec 



Aucun document lié à cet événement.

Retour
Retour à l'index