A finer reduction of constraint problems to digraphs
From MaRDI portal
Publication:3460423
DOI10.2168/LMCS-11(4:18)2015zbMath1409.05094arXiv1406.6413OpenAlexW1791050365MaRDI QIDQ3460423
Dejan Delić, Marcel Jackson, Jakub Bulín, Todd Niven
Publication date: 7 January 2016
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1406.6413
Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Automorphisms and endomorphisms of algebraic structures (08A35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, On the complexity of \(\mathbb{H}\)-coloring for special oriented trees, Unnamed Item, The smallest hard trees, Binarisation for Valued Constraint Satisfaction Problems, Reflexive digraphs with near unanimity polymorphisms, The Complexity of Valued CSPs, Algebra and the Complexity of Digraph CSPs: a Survey, Algebraic foundations for qualitative calculi and networks, Galois connections for patterns: an algebra of labelled graphs, The number of clones determined by disjunctions of unary relations