Atlas home ||
Conferences |
Abstracts |
about Atlas
Algebraic structures in combinatorial problems
by
Bulatov Andrei
Ural State University (Russia)
Constraint Satisfaction Problem provides a framework in which a
wide variety
of combinatorial problems can be expressed in a natural way.
The aim in a constraint satisfaction
problem is to assign
values to a given set of variables such that certain constraints
satisfied on
the values that can be assigned simulteneously to some subsets of
variables.
P.Jeavons and coauthors develope
an approach to study constraint satisfaction problems which is based on
characterising of the complexity of problem classes via certain
algebraic
objects. In particular, each subclass of constraint satisfaction
problem
with finite set of values may be assigned a finite algebra such that
the complexity of the subclass depends only on the algebra.
We show how the complexity of problem classes is connected with
properties
of locally finite varieties.
Date received: December 22, 2000
Copyright © 2000 by the author(s).
The author(s) of this document and the organizers of the conference
have granted their consent to include this abstract in
Atlas Conferences Inc.
Document # cafo-36.