Local-Generator : "diviser pour régner" pour l'extraction des traverses minimales d'un hypergraphe

Christine Largeron 1 Sadok Ben Yahia 2 Nidhal Jelassi 1, 2
1 LHC - Laboratoire Hubert Curien [Saint Etienne]
2 Faculté des Sciences de Tunis
Résumé : Du fait qu'elles apportent des solutions dans de nombreuses applications, les traverses minimales des hypergraphes ne cessent de susciter l'intérêt de la communauté scientifique et le développement d'algorithmes pour les calculer. Dans cet article, nous présentons une nouvelle approche pour l'optimisation de l'extraction des traverses minimales basée sur les notions d'hypergraphe partiel et de traverses minimales locales selon une stratégie diviser pour régner. Nous introduisons aussi un nouvel algorithme, appelé LOCAL-GENERATOR pour le calcul des traverses minimales. Les expérimentations effectuées sur divers jeux de données ont montré l'intérêt de notre approche, notamment sur les hypergraphes ayant un nombre de transversalité élevé et renfermant un nombre très important de traverses minimales.
Mots-clés : Hypergraphe traverse minimale nombre de transversalité hypergraphe partiel
Type de document :
Communication dans un congrès
Actes de la conférence Extraction et gestion des connaissances (EGC 2014), Jan 2014, Rennes, France. pp.245-256, 2014
Liste complète des métadonnées
https://hal-ujm.archives-ouvertes.fr/ujm-01017655
Contributeur : Christine Largeron <>
Soumis le : mercredi 2 juillet 2014 - 21:44:13
Dernière modification le : mercredi 25 juillet 2018 - 14:05:31

Identifiants

  • HAL Id : ujm-01017655, version 1

Collections

UNIV-ST-ETIENNE | LAHC | IOGS | PARISTECH

Citation

Christine Largeron, Sadok Ben Yahia, Nidhal Jelassi. Local-Generator : "diviser pour régner" pour l'extraction des traverses minimales d'un hypergraphe. Actes de la conférence Extraction et gestion des connaissances (EGC 2014), Jan 2014, Rennes, France. pp.245-256, 2014. 〈ujm-01017655〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

123

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD