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 12 Juin 2012

Recherche des noyaux d'un graphe aléatoire

par Jean-Marie Le Bars (GREYC)

Le noyau d'un graphe est un sous-ensemble de l'ensemble des sommets à la fois stable et dominant.

Le problème de décider si un graphe possède un noyau est NP-complet, mais cela ne garantit pas qu'il est facile d'obtenir des distributions naturelles produisant des instances difficiles (les algorithmes connus ne sont pas polynomiaux).

Nous nous intéresserons aux distributions obtenues avec le célèbre modèle d'Erdös et Rényi, le modèle G(n, p) : n est le nombre de sommets et p la probabilité d'arc : on met un arc entre deux sommets avec la probabilité p, où p est fixé ou fonction de n.

Nous verrons que les tailles possibles des noyaux d'un graphe de G(n, p) varient fortement selon la valeur de p et que le cas p = cn semble fournir les instances les plus difficiles.

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