Victor Dalmau - Generalized Majority-Minority Operations are Tractable

lmcs:2237 - Logical Methods in Computer Science, September 28, 2006, Volume 2, Issue 4 - https://doi.org/10.2168/LMCS-2(4:1)2006
Generalized Majority-Minority Operations are TractableArticle

Authors: Victor Dalmau

    Generalized majority-minority (GMM) operations are introduced as a common generalization of near unanimity operations and Mal'tsev operations on finite sets. We show that every instance of the constraint satisfaction problem (CSP), where all constraint relations are invariant under a (fixed) GMM operation, is solvable in polynomial time. This constitutes one of the largest tractable cases of the CSP.


    Volume: Volume 2, Issue 4
    Published on: September 28, 2006
    Submitted on: January 4, 2006
    Keywords: Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,F.4.1

    23 Documents citing this article

    Consultation statistics

    This page has been seen 1113 times.
    This article's PDF has been downloaded 296 times.