Réinitialiser mot de passe
E-mail
Password
RNTI

MODULAD
Représentations compactes des graphes et contraintes pseudo booléennes
In EGC 2019, vol. RNTI-E-35, pp.407-412
Résumé
Les graphes représentent un outil efficace pour la modélisation des
relations structurelles entre les objets. Cependant, l’exploitation de ces graphes
de données est très coûteuse en raison de la taille. En effet, dans la plupart
des applications réelles, la taille des graphes est largement grande, ce qui rend
difficile à comprendre l’information et la structure codée dans ces graphes par
une simple visualisation. La représentation compacte des grands graphes, appelée
aussi compression des graphes, est une opération qui permet la diminution
du nombre d’arêtes ou de noeuds du graphe pour faciliter leurs traitements.
Dans cet article, nous proposons une nouvelle approche basée sur l’utilisation
des contraintes pseudo booléennes pour une représentation condensée de larges
graphes. L’avantage d’une telle représentation est qu’au lieu de représenter un
graphe (e.g., clique) par un nombre quadratique d’arêtes, on peut l’exprimer sous
forme d’une inéquation linéaire dont les modèles correspondent exactement aux
arêtes du graphe initial. Notre approche permet le passage à l’échelle tout en
garantissant la décompression de graphes par une simple résolution des inéquations
linéaires correspondantes. Les expérimentation sur plusieurs graphes réels
montrent que notre approche offre de meilleures performances comparée à plusieurs
approches de l’état de l’art.