- ...NP-complet
- L'appartenance à NP est immédiate, la
complétude s'obtient par restriction au problème PARTITION
correspondant aux cas où l'une des 2 enzymes produit deux segments de même
longueur [ Gol 87].
- ...micro-structure
- La micro-structure ou Graphe de consistence
est une représentation du CSP par un graphe dont les sommets représentent
les valeurs et les arêtes relient des paires de valeurs compatibles
Auteurs:Christine Gaspin, Christian Bessiere, Annick Moisan et Thomas Schiex
Dernière mise à jour: jeudi, 11 janvier 1996, 18:28:04 MET
Institut National de la Recherche Agronomique
Département de Biométrie et Intelligence Artificielle
Copyright(C)1995
INRA
Tous droits réservés