Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Publications
Theses and dissertations
Ad Astra association
 
Press releases
News
Events
Funding opportunities
 
Login
Registration
 
>> 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

URL: http://www.springerlink.com/link.asp?id=d4233vp3028g3n83

Posted by Gabriel Istrate

Back

   
© Ad Astra 2001-2013