Browsing Research publications by Author "Dalmau, Víctor"

Now showing items 1-3 of 3

    • Caterpillar duality for constraint satisfaction problems 

      Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei (IEEE, 2008)

    • CD(4) has bounded width 

      Carvalho, Catarina; Dalmau, Víctor; Marković, Petar; Maróti, Miklós (2009)
      We prove that the constraint languages invariant under a short sequence of J\'onsson terms (containing at most three non-trivial ternary terms) are tractable by showing that they have bounded width. This improves the ...

    • CSP duality and trees of bounded pathwidth 

      Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei (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 ...