Inscriere cercetatori

Daca aveti cont Ad Astra si de Facebook, intrati pe pagina de profil pentru a da dreptul sa va logati pe site doar cu acest buton.

Site nou !

Daca nu va puteti recupera parola (sau aveti alte probleme), scrieti-ne la pagina de contact. Situl vechi se gaseste la adresa


Counting, Structure Identification and Maximum Consistency for Binary Constraint Satisfaction Problems

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în volumul unei conferinţe

Autori: Gabriel Istrate

Editorial: G. Smolka, Springer Verlag, Lecture Notes in Computer Science 1330, Proceedings of the Third International Conference on Principles and Practice of Constraint Programming - CP 1997, Linz, Austria, p.136-149, 1997.


Want create site? Find Free WordPress Themes and plugins.

Using a framework inspired by Schaefer’s generalized satisfiability model [Sch78], Cohen, Cooper and Jeavons [CCJ94] studied the computational complexity of constraint satisfaction problems in the special case when the set of constraints is closed under permutation of labels and domain restriction, and precisely identified the tractable (and intractable) cases.
Using the same model we characterize the complexity of three related problems:
1. counting the number of solutions.
2. structure identification (Dechter and Pearl [DP92]).
3. approximating the maximum number of satisfiable constraints.

Did you find apk for android? You can find new Free Android Games and apps.

Cuvinte cheie: constraint programming, computational complexity