Galois connections for patterns: an algebra of labelled graphs
From MaRDI portal
Publication:2044173
DOI10.1007/978-3-030-72308-8_9zbMath1467.68176OpenAlexW3138348664MaRDI QIDQ2044173
Peter G. Jeavons, Martin C. Cooper, Stanislav Živný, David A. Cohen
Publication date: 4 August 2021
Full work available at URL: https://doi.org/10.1007/978-3-030-72308-8_9
Graph theory (including graph drawing) in computer science (68R10) Knowledge representation (68T30) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Galois correspondences, closure operators (in relation to ordered sets) (06A15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems
- Tractability in constraint satisfaction problems: a survey
- A strong Mal'cev condition for locally finite varieties omitting the unary type
- Hybrid tractability of valued constraint problems
- Monadic second-order evaluations on tree-decomposable graphs
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- Tree clustering for constraint networks
- On the algebraic structure of combinatorial problems
- Characterising tractable constraints
- Binary constraint satisfaction problems defined by excluded topological minors
- On singleton arc consistency for CSPs defined by monotone patterns
- Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
- Domain permutation reduction for constraint satisfaction problems
- Forbidden lifts (NP and CSP for combinatorialists)
- The Tractability of CSP Classes Defined by Forbidden Patterns
- A finer reduction of constraint problems to digraphs
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- A sufficient condition for backtrack-bounded search
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Hybrid Tractable Classes of Constraint Problems
- A Proof of the CSP Dichotomy Conjecture
- Classifying the Complexity of Constraints Using Finite Algebras
- Binarisation for Valued Constraint Satisfaction Problems
- Tractable constraints on ordered domains
