A polynomial-time algorithm for near-unanimity graphs

DOI10.1016/J.JALGOR.2004.04.011zbMATH Open1101.68960OpenAlexW1992517803MaRDI QIDQ3022752FDOQ3022752

Cynthia Loten, L. Zádori, Benoît Larose

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
• Absolute retracts and varieties generated by chordal graphs
• Colouring, constraint satisfaction, and complexity
• Semilattice polymorphisms and chordal graphs
• NU Polymorphisms on Reflexive Digraphs
• Recolouring reflexive digraphs
• Algebra and the Complexity of Digraph CSPs: a Survey
• Reflexive digraphs with near unanimity polymorphisms
• Weak near-unanimity functions and digraph homomorphism problems
• Reflexive graphs with near unanimity but no semilattice polymorphisms
• Reconfiguration of homomorphisms to reflexive digraph cycles
• The existence of a near-unanimity function is decidable
• Voting 'Against' in regular and nearly regular graphs

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)