 |
Université Jean Monnet – Saint-Etienne |  |
Conference papers
Local-Generator : "diviser pour régner" pour l'extraction des traverses minimales d'un hypergraphe
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.
https://hal-ujm.archives-ouvertes.fr/ujm-01017655
Contributor : Christine Largeron Connect in order to contact the contributor
Submitted on : Wednesday, July 2, 2014 - 9:44:13 PM
Last modification on : Wednesday, October 28, 2020 - 2:20:03 PM
Contributor : Christine Largeron Connect in order to contact the contributor
Submitted on : Wednesday, July 2, 2014 - 9:44:13 PM
Last modification on : Wednesday, October 28, 2020 - 2:20:03 PM