Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability

DOI10.1137/S0895480199383353zbMath0982.05097OpenAlexW1969223164MaRDI QIDQ2753538

Tomás Feder

Publication date: 11 November 2001

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480199383353

zbMATH Keywords

Boolean satisfiabilityconstraint satisfactiondigraph homomorphismoriented cycles

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph theory (05C99) Directed graphs (digraphs), tournaments (05C20)

Related Items (17)

Dichotomies for classes of homomorphism problems involving unary functions ⋮ Minimum cost homomorphism dichotomy for oriented cycles ⋮ List homomorphisms to reflexive graphs ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ The smallest hard trees ⋮ Minimum Cost Homomorphism Dichotomy for Oriented Cycles ⋮ Colouring, constraint satisfaction, and complexity ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ The complexity of tropical graph homomorphisms ⋮ Building blocks for the variety of absolute retracts ⋮ Dichotomy for finite tournaments of mixed-type ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ CSP dichotomy for special triads ⋮ Adjusted Interval Digraphs ⋮ Peek arc consistency ⋮ Dualities for Constraint Satisfaction Problems ⋮ CSP DICHOTOMY FOR SPECIAL POLYADS

This page was built for publication: Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability