Galois connections for patterns: an algebra of labelled graphs

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

zbMATH Keywords

Galois connection; lattices; constraint satisfaction; tractability; forbidden patterns

Mathematics Subject Classification ID

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