CSP duality and trees of bounded pathwidth
From MaRDI portal
Publication:986555
DOI10.1016/j.tcs.2010.05.016zbMath1196.68167OpenAlexW2138857669MaRDI QIDQ986555
Andrei A. Krokhin, Catarina A. Carvalho, Victor Dalmau
Publication date: 11 August 2010
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10230/36329
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (5)
A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\) ⋮ Unnamed Item ⋮ The smallest hard trees ⋮ The complexity of the list homomorphism problem for graphs ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
Cites Work
- Unnamed Item
- An annotated bibliography on guaranteed graph searching
- Bounded width problems and algebras
- Existence theorems for weakly symmetric operations
- Universal algebra and hardness results for constraint satisfaction problems
- Chromatically optimal rigid graphs
- The vertex separation number of a graph equals its path-width
- Graph searching and a min-max theorem for tree-width
- The vertex separation and search number of a graph
- Algebraic properties and dismantlability of finite posets
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Searching and pebbling
- Monotone Jónsson operations and near unanimity functions
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- Majority constraints have bounded pathwidth duality
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- Marshals, monotone marshals, and hypertree-width
- First-order Definable Retraction Problems for Posets and Reflexive Graphs
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The complexity of searching a graph
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Posets, near unanimity functions and zigzags
- The Complexity of the Extendibility Problem for Finite Posets
- Constraint Satisfaction Problems of Bounded Width
- Recontamination does not help to search a graph
- Linear Datalog and Bounded Path Duality of Relational Structures
- Classifying the Complexity of Constraints Using Finite Algebras
- Recent Results on the Algebraic Approach to the CSP
- Dualities for Constraint Satisfaction Problems
- Graph-Theoretic Concepts in Computer Science
- Idempotent totally symmetric operations on finite posets
This page was built for publication: CSP duality and trees of bounded pathwidth
