Galois connections for patterns: an algebra of labelled graphs
From MaRDI portal
Publication:2044173
DOI10.1007/978-3-030-72308-8_9zbMath1467.68176MaRDI 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
68R10: Graph theory (including graph drawing) in computer science
68T30: Knowledge representation
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
06A15: Galois correspondences, closure operators (in relation to ordered sets)
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