Title :
Constraint Satisfaction Problems of Bounded Width
Author :
Barto, Libor ; Kozik, Marcin
Author_Institution :
Dept. of Algebra, Charles Univ., Prague, Czech Republic
Abstract :
We provide a full characterization of applicability of The Local Consistency Checking algorithm to solving the non-uniform Constraint Satisfaction Problems. This settles the conjecture of Larose and Zadori.
Keywords :
combinatorial mathematics; computational complexity; constraint theory; bounded width; local consistency checking algorithm; nonuniform constraint satisfaction problem; Algebra; Artificial intelligence; Computational complexity; Computer science; Constraint theory; Electrooculography; Equations; Polynomials; bounded width; constraint satisfaction problem; local consistency;
Conference_Titel :
Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on
Conference_Location :
Atlanta, GA
Print_ISBN :
978-1-4244-5116-6
DOI :
10.1109/FOCS.2009.32
