Details

Autor(en) / Beteiligte

• Istrate, Gabriel
• Smolka, Gert

Titel

Counting, structure identification and maximum consistency for binary constraint satisfaction problems

Ist Teil von

• Lecture notes in computer science, 1997, p.136-149

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

1997

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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:counting the number of solutions.structure identification (Dechter and Pearl [DP92]).approximating the maximum number of satisfiable constraints.