Dans cet article, nous considérons le problème de la cohérence des réseaux de contraintes qualitatives pour le temps et l'espace. La méthode la plus efficace pour résoudre ce problème consiste à utiliser un algorithme de recherche mettant en oeuvre d'une part la méthode de fermeture par faible composition comme propagation locale de contraintes et d'autre part une décomposition des contraintes en relations appartenant à une classe traitable. Nous proposons une extension de cet algorithme basée sur la notion d'éligibilité de contraintes. Nous étudions cet algorithme de manière théorique et de manière expérimentale.