Reflexive digraphs with near unanimity polymorphisms
From MaRDI portal
Publication:442320
DOI10.1016/j.disc.2012.03.040zbMath1245.05059MaRDI QIDQ442320
Publication date: 10 August 2012
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2012.03.040
constraint satisfaction; (1; 2)-consistency checking algorithm; gumm and totally symmetric idempotent polymorphisms; Jonsson; near unanimity; reflexive digraphs
Related Items
NU Polymorphisms on Reflexive Digraphs, n-Permutability is not join-prime for n ≥ 5, Algebra and the Complexity of Digraph CSPs: a Survey, Between an n-ary and an n + 1-ary near-unanimity term, On the use of majority for investigating primeness of 3-permutability, Preserving near unanimity terms under products, List-homomorphism problems on graphs and arc consistency, The structure of polynomial operations associated with smooth digraphs., The fixed vertex property for graphs, Recolouring reflexive digraphs, The fixed point property for ordered sets, Reflexive graphs with near unanimity but no semilattice polymorphisms, Reconfiguration of homomorphisms to reflexive digraph cycles, Semilattice polymorphisms and chordal graphs, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maltsev digraphs have a majority polymorphism
- A fixed point theorem for finite partially orderes sets
- Algebraic properties and dismantlability of finite posets
- Jónsson terms and near-unanimity functions in finite posets
- Monotone Jónsson operations and near unanimity functions
- Few subpowers, congruence distributivity and near-unanimity terms
- A polynomial-time algorithm for near-unanimity graphs
- A finer reduction of constraint problems to digraphs
- Monotone clones, residual smallness and congruence distributivity
- Congruence Distributivity Implies Bounded Width
- The structure of finite algebras
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Relational Sets and Categorical Equivalence of Algebras
- Tractability and Learnability Arising from Algebras with Few Subpowers
- Order varieties and monotone retractions of finite posets