Browsing by Author "Krokhin, Andrei"

Sort by: Order: Results:

  • Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei (Elsevier, 2010)
    We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of ...
  • Dalmau, Víctor; Krokhin, Andrei (Elsevier, 2008)
    We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that ...
  • Dalmau, Víctor; Krokhin, Andrei; Larose, Benoit (Elsevier, 2008)
    The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study ...
  • Dalmau, Víctor; Krokhin, Andrei; Manokaran, Rajsekar (SIAM (Society for Industrial and Applied Mathematics), 2015)
    We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language Γ on an arbitrary finite domain. The goal in such a problem is to minimize the number of unsatisfied ...