CSP dichotomy for special triads
From MaRDI portal
Publication:3395563
DOI10.1090/S0002-9939-09-09883-9zbMath1215.05179MaRDI QIDQ3395563
Marcin Kozik, Libor Barto, Todd Niven, Miklós Maróti
Publication date: 11 September 2009
Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)
Related Items (10)
Residual properties of pre-bipartite digraphs ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ The smallest hard trees ⋮ On Maltsev Digraphs ⋮ On Maltsev digraphs ⋮ Graph partitions with prescribed patterns ⋮ Smooth digraphs modulo primitive positive constructability and cyclic loop conditions ⋮ Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems ⋮ CSP DICHOTOMY FOR SPECIAL POLYADS ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The effect of two cycles on the complexity of colourings by directed graphs
- Existence theorems for weakly symmetric operations
- On the complexity of H-coloring
- On multiplicative graphs and the product conjecture
- Polynomial graph-colorings
- Complexity of tree homomorphisms
- Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Duality and Polynomial Testing of Tree Homomorphisms
- Classifying the Complexity of Constraints Using Finite Algebras
- Universal Algebra and Hardness Results for Constraint Satisfaction Problems
This page was built for publication: CSP dichotomy for special triads
