List-homomorphism problems on graphs and arc consistency
From MaRDI portal
Publication:393914
DOI10.1016/j.disc.2013.07.018zbMath1281.05069OpenAlexW2076955343MaRDI QIDQ393914
Adrien Lemaître, Benoit Larose
Publication date: 24 January 2014
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2013.07.018
arc-consistencylist-homomorphism problemsretraction problemssymmetric Datalogtotally symmetric operations
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)
Related Items (3)
Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reflexive digraphs with near unanimity polymorphisms
- Absolute reflexive retracts and absolute bipartite retracts
- The complexity of the list homomorphism problem for graphs
- Universal algebra and hardness results for constraint satisfaction problems
- Circular-arc graphs with clique cover number two
- Majority constraints have bounded pathwidth duality
- Approximation of Minimum Cost Homomorphisms
- A polynomial-time algorithm for near-unanimity graphs
- Graphs Admitting $k$-NU Operations. Part 2: The Irreflexive Case
- Directed st-Connectivity Is Not Expressible in Symmetric Datalog
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Bi‐arc graphs and the complexity of list homomorphisms
- Constraint Satisfaction Problems of Bounded Width
- Classifying the Complexity of Constraints Using Finite Algebras
- Computational Complexity
- A Characterisation of First-Order Constraint Satisfaction Problems
- Recent Results on the Algebraic Approach to the CSP
- Dualities for Constraint Satisfaction Problems
This page was built for publication: List-homomorphism problems on graphs and arc consistency