Reflexive digraphs with near unanimity polymorphisms

DOI10.1016/j.disc.2012.03.040zbMath1245.05059OpenAlexW2073159267MaRDI 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(12)-consistency checking algorithmgumm and totally symmetric idempotent polymorphismsJonssonnear unanimityreflexive digraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (16)

Unnamed Item ⋮ Preserving near unanimity terms under products ⋮ The fixed point property for ordered sets ⋮ List-homomorphism problems on graphs and arc consistency ⋮ The fixed vertex property for graphs ⋮ Surjective polymorphisms of directed reflexive cycles ⋮ NU Polymorphisms on Reflexive Digraphs ⋮ Semilattice polymorphisms and chordal graphs ⋮ n-Permutability is not join-prime for n ≥ 5 ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ The structure of polynomial operations associated with smooth digraphs. ⋮ Recolouring reflexive digraphs ⋮ Reflexive graphs with near unanimity but no semilattice polymorphisms ⋮ Reconfiguration of homomorphisms to reflexive digraph cycles ⋮ Between an n-ary and an n + 1-ary near-unanimity term ⋮ On the use of majority for investigating primeness of 3-permutability

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

This page was built for publication: Reflexive digraphs with near unanimity polymorphisms