Détection efficace des traverses minimales d'un hypergraphe par élimination de la redondance
Résumé
L'extraction des traverses minimales d'un hypergraphe est une problématique réputée comme particulièrement difficile et qui a fait l'objet de plusieurs travaux dans la littérature. Dans cet article, nous établissons un lien entre les concepts de la fouille de données et ceux de la théorie des hypergraphes, proposant ainsi un cadre méthodologique pour le calcul des traverses minimales. Le nombre de ces traverses minimales étant, souvent, exponentiel même pour des hypergraphes simples, nous proposons d'en représenter l'ensemble de manière concise et exacte. Pour ce faire, nous introduisons la notion de traverses minimales irrédondantes, à partir desquelles nous pouvons retrouver l'ensemble global de toutes les traverses minimales, à l'aide de l'algorithme IMT-EXTRACTOR. Une étude expérimentale de ce nouvel algorithme a confirmé l'intérêt de l'approche introduite