Charles Explorer logo
🇨🇿

Polymorphisms of small digraphs

Publikace na Matematicko-fyzikální fakulta |
2011

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

For each digraph with at most 5 vertices, we provide a list of its polymorphisms interesting with respect to the complexity of the corresponding Constraint Satisfaction Problem. We find a digraph on six vertices such that the complexity of its retraction problem is unknown with current techniques; this is the smallest such example.