Algorithmes Optimaux et Sous-optimaux de Singleton Consistance d'Arc

International audienceLa singleton consistance d'arc (SAC) permet de filtrer bien plus que la consistance d'arc en s'assurant qu'aucune affectation ne puisse rendre le réseau de contraintes arc inconsistant. Des algorithmes ont été proposés pour réaliser la fermeture par singleton consistance d'arc mais avec des complexités temporelles clairement non optimales. Dans cet article, nous donnons une borne inférieure de la complexité temporelle dans le pire des cas des algorithmes de singleton consistance d'arc. Nous proposons un algorithme possédant cette borne pour complexité temporelle. Cet algorithme optimal est cependant coûteux en espace. C'est pourquoi nous proposons également un algorithme troquant l'optimalité temporelle pour une meilleure complexité spatiale. Bien que non optimal, ce dernier possède une complexité temporelle dans le pire des cas inférieure à celle de tous les algorithmes de singleton consistance d'arc déjà publiés. Une étude expérimentale met en valeur les bonnes performances des algorithmes proposés