Reflexive digraphs with near unanimity polymorphisms

DOI10.1016/j.disc.2012.03.040zbMath1245.05059MaRDI QIDQ442320

Miklós Maróti, László Zádori

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

zbMATH Keywords

constraint satisfaction; (1; 2)-consistency checking algorithm; gumm and totally symmetric idempotent polymorphisms; Jonsson; near unanimity; reflexive digraphs

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

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