Contributions à la coloration des hypergraphes basées sur les traverses minimales.

Résumé : Dans cet article, nous nous intéressons à la problématique de la coloration d’hypergraphes en l’abordant suivant une approche originale, qui met en lumière le lien qui existe entre le nombre chromatique et les traverses minimales. Nous proposons deux algorithmes TM2COLORS et TMXCOLORS. Le premier permet de vérifier si un hypergraphe possède la propriété de 2- coloriabilité. Le second est une extension du premier qui calcule le nombre chromatique de l’hypergraphe d’entrée. Notons qu’un des avantages de l’approche que nous proposons, par rapport à la majorité des méthodes existantes, est qu’elle est applicable à n’importe quel type d’hypergraphe, qu’il soit bipartite, k-uniforme, dense ou aléatoire.
Type de document :
Communication dans un congrès
EGC, Jan 2016, Reims, France. RNTI, Conférence Extraction et Gestion des Connaissances ( EGC), pp.547-548, 2016, 〈http://egc2016.univ-reims.fr/index.php/Pr%C3%A9sentation〉
Liste complète des métadonnées

https://hal-auf.archives-ouvertes.fr/hal-01391799
Contributeur : Christine Largeron <>
Soumis le : jeudi 3 novembre 2016 - 18:46:46
Dernière modification le : jeudi 11 janvier 2018 - 06:20:36

Identifiants

  • HAL Id : hal-01391799, version 1

Collections

Citation

Mohamed Nidhal Jelassi, Sadok Ben Yahia, Christine Largeron. Contributions à la coloration des hypergraphes basées sur les traverses minimales. . EGC, Jan 2016, Reims, France. RNTI, Conférence Extraction et Gestion des Connaissances ( EGC), pp.547-548, 2016, 〈http://egc2016.univ-reims.fr/index.php/Pr%C3%A9sentation〉. 〈hal-01391799〉

Partager

Métriques

Consultations de la notice

61