Beyond bounded width and few subpowers
Speaker:
Miklos Maroti, University of Szeged
Date and Time:
Wednesday, August 3, 2011 - 9:30am to 10:30am
Abstract:
There are two important algorithms for solving constraint satisfaction problems (CSP) over restricted classes of algebras. One is the (2, 3) consistency algorithm for solving instances of the CSP where the algebras are in a congruence meet-semidistributive variety. The other is the generalized Gaussian elimination algorithm for solving instances of the CSP where the algebras have few subpowers (equivalently have edge terms). We present two new algorithms, one that combines the (2, 3) consistency algorithm with the generalized Gaussian elimination algorithm, and the other is a new reduction technique that uses consistent set of unary polynomials.