A polynomial-time algorithm for near-unanimity graphs

DOI10.1016/j.jalgor.2004.04.011zbMath1101.68960OpenAlexW1992517803MaRDI QIDQ3022752

Cynthia Loten, Benoit Larose, László Zádori

Publication date: 30 June 2005

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.04.011

zbMATH Keywords

Polynomial-time algorithmNear-unanimity operationReflexive graph

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

List-homomorphism problems on graphs and arc consistency ⋮ NU Polymorphisms on Reflexive Digraphs ⋮ Reflexive digraphs with near unanimity polymorphisms ⋮ Semilattice polymorphisms and chordal graphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ The existence of a near-unanimity function is decidable ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Recolouring reflexive digraphs ⋮ Reflexive graphs with near unanimity but no semilattice polymorphisms ⋮ Absolute retracts and varieties generated by chordal graphs ⋮ Reconfiguration of homomorphisms to reflexive digraph cycles

This page was built for publication: A polynomial-time algorithm for near-unanimity graphs