Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 16 Octobre 2007

Complétions d'intervalles minimales et largeur linéaire (pathwidth) des graphes

par Ioan Todinca (LIFO - Université d'Orléans)

Les graphes étant des objets complexes, on tente souvent de les "simplifier" si possible sans leur apporter beaucoup de modifications. Une technique courante consiste à rajouter des arêtes au graphe en entrée afin d'obtenir un graphe plus simple.

Une complétion d'intervalles d'un graphe quelconque G est un graphe d'intervalles H, obtenu à partir de G en lui rajoutant des arêtes. On cherche classiquement à minimiser certains paramètres comme le nombre d'arêtes rajoutées ou la taille de la clique de cardinal maximum de H. Ces problèmes étant NP-difficiles, nous nous intéressons aux complétion d'intervalles minimales, où l'on demande simplement à ce que l'ensemble d'arêtes ajoutées soit minimal par inclusion. Je montrerai comment calculer une telle complétion et j'évoquerai des applications au calcul de la largeur linéaire pour des graphes particuliers.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr