Dichotomy for finite tournaments of mixed-type

DOI10.1016/J.DISC.2015.06.024MaRDI QIDQ2515599zbMATH OpenOpenAlexFDO

Authors Alexander Wires

Publication date 5 August 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2015.06.024

zbMATH Keywords

complexity dichotomyconstraint satisfactiondigraph homomorphismpolymorphismtournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Recommendations

• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• scientific article; zbMATH DE number 5030273
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• scientific article; zbMATH DE number 1985566
• On finite Taylor algebras

Cites work

• H-coloring dichotomy revisited
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A quasi-Mal'cev condition with unexpected application.
• Characterizations of several Maltsev conditions.
• Classification of homomorphisms to oriented cycles and of k-partite satisfiability
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Combinatorial problems raised from 2-semilattices
• Complexity of conservative constraint satisfaction problems
• Complexity of tree homomorphisms
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Duality and Polynomial Testing of Tree Homomorphisms
• Existence theorems for weakly symmetric operations
• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 5030273 (Why is no real title available?)
• scientific article; zbMATH DE number 3293648 (Why is no real title available?)
• On the complexity of H-coloring
• On the complexity of the general coloring problem
• On the reduction of the CSP dichotomy conjecture to digraphs
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• The complexity of colouring by locally semicomplete digraphs
• The Complexity of Colouring by Semicomplete Digraphs
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Tractability and learnability arising from algebras with few subpowers
• Universal algebra. Fundamentals and selected topics
• Weak near-unanimity functions and digraph homomorphism problems

Cited in

(4)

• Indecomposability and duality of tournaments
• scientific article; zbMATH DE number 1823770 (Why is no real title available?)
• Algebra and the complexity of digraph CSPs: a survey
• Quantified Constraints in Twenty Seventeen

This page was built for publication: Dichotomy for finite tournaments of mixed-type

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