Personal tools
You are here: Home GT Dodola Fouille d'objets modélisés par des graphes : les méthodes d'extraction des sous-graphes fréquents.
Document Actions

Fouille d'objets modélisés par des graphes : les méthodes d'extraction des sous-graphes fréquents.

What Meeting
When 2008-11-25
from 14:30 to 15:30
Where S3-365
Add event to calendar vCal (Windows, Linux)
iCal (Mac OS X)
by François Rioult last modified 2008-11-18 01:12
par Guillaume Poezevara, doctorant au GREYC.

L'exposé concernera les méthodes de recherche des sous-graphes apparaissant fréquemment au sein d'une famille de graphes. Le problème de la recherche des sous-graphes fréquents peut s'énoncer de la manière suivante : étant donnés une famille de graphes F et un seuil de fréquence s, trouver tous les graphes qui apparaissent dans s graphes de F.

La recherche de sous graphes fréquents candidats a une complexité exponentielle. D'ailleurs elle inclut le problème d'isomorphisme de sous graphe qui est NP-complet. Si on considère l'extraction de sous-graphes fréquents comme une généralisation du test de l'isomorphisme de sous-graphe, on se convainc rapidement de la nature fortement combinatoire du problème et de la complexité des algorithmes destinés à l'extraction.

Depuis une dizaine d'années, plusieurs méthodes ont été proposées pour découvrir les sous-graphes fréquents. Ces méthodes peuvent se classer en deux familles. Nous proposons pour ce groupe de travail de les présenter et d'en étudier les caractéristiques. Pour cela nous nous appuyerons sur une étude plus approfondie d'un algorithme de chaque famille (AGM et gSpan)."

« June 2011 »
Su Mo Tu We Th Fr Sa
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30
 

Powered by Plone, the Open Source Content Management System

This site conforms to the following standards: