Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Theses and dissertations
Ad Astra association
Press releases
Funding opportunities
>> Românã

Gabriel Istrate. Counting, Structure Identification and Maximum Consistency for Binary Constraint Satisfaction Problems. In G. Smolka (ed.), Proceedings of the Third International Conference on Principles and Practice of Constraint Programming - CP 1997, Linz, Austria, pp. 136-149. Springer Verlag, Lecture Notes in Computer Science 1330, 1997.

Abstract: 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.

Keywords: constraint programming, computational complexity


Posted by Gabriel Istrate


© Ad Astra 2001-2013