A polynomial-time algorithm for near-unanimity graphs

DOI10.1016/J.JALGOR.2004.04.011MaRDI QIDQ3022752zbMATH OpenOpenAlexFDO

Authors Benoît Larose, Cynthia Loten, L. 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

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

Cited in

(13)

• List-homomorphism problems on graphs and arc consistency
• Voting 'Against' in regular and nearly regular graphs
• Absolute retracts and varieties generated by chordal graphs
• Colouring, constraint satisfaction, and complexity
• Semilattice polymorphisms and chordal graphs
• Recolouring reflexive digraphs
• Reflexive digraphs with near unanimity polymorphisms
• Weak near-unanimity functions and digraph homomorphism problems
• NU polymorphisms on reflexive digraphs
• Reflexive graphs with near unanimity but no semilattice polymorphisms
• Reconfiguration of homomorphisms to reflexive digraph cycles
• Algebra and the complexity of digraph CSPs: a survey
• The existence of a near-unanimity function is decidable

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3022752)