Atlas home || Conferences | Abstracts | about Atlas

AAA76 - 76th Workshop on General Algebra (76. Arbeitstagung Allgemeine Algebra)
May 22-25, 2008
Department of Algebra, Johannes Kepler University Linz
Linz, Austria

Organizers
Erhard Aichinger, Peter Mayr, Matt Nickodemus, Günter Pilz

View Abstracts
Conference Homepage

CSP and NU(4)
by
Libor Barto
Charles University in Prague
Coauthors: Marcin Kozik

Let H be a fixed (finite) directed graph. CSP(H) is the following decision problem:

INPUT: A directed graph G
OUTPUT: Is there a homomorphism G → H?

The properties of CSP(H) (computational complexity, algorithms which can solve the problem) heavily depend on the operations compatible with the graph H. We show special properties of CSP(H) for graphs H admitting a 4-ary near unanimity operation.

Date received: May 7, 2008

Copyright © 2008 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 # cawc-46.