Characterising tractable constraints
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A Sufficient Condition for Backtrack-Free Search
- A generic arc-consistency algorithm and its specializations
- A sufficient condition for backtrack-bounded search
- An optimal k-consistency algorithm
- Comments on Mohr and Henderson's path consistency algorithm
- Consistency in networks of relations
- Constraint relaxation may be perfect
- Decomposing constraint satisfaction problems using database techniques
- Fast parallel constraint satisfaction
- From local to global consistency
- Network-based heuristics for constraint-satisfaction problems
- Networks of constraints: Fundamental properties and applications to picture processing
Cited in
(58)- Local and global relational consistency
- An algebraic characterization of tractable constraints
- Implementing a test for tractability
- Learnability of quantified formulas.
- Parameterized complexity of the workflow satisfiability problem
- Tractability in constraint satisfaction problems: a survey
- Quantified Constraints and Containment Problems
- On singleton arc consistency for CSPs defined by monotone patterns
- A hybrid tractable class for non-binary CSPs
- On singleton arc consistency for CSPs defined by monotone patterns
- Colouring, constraint satisfaction, and complexity
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- Dualities for Constraint Satisfaction Problems
- Tractable set constraints
- Pushing the frontier of minimality
- CSP beyond tractable constraint languages
- Graph matching problems and the NP-hardness of sortedness constraints
- New tractable classes from old
- Tractable constraints on ordered domains
- A polynomial relational class of binary CSP
- How to determine the expressive power of constraints
- scientific article; zbMATH DE number 7270290 (Why is no real title available?)
- Constraints, consistency and closure
- On the algebraic structure of combinatorial problems
- Constraint reasoning
- On the Tractability of Smooth Constraint Satisfaction Problems
- scientific article; zbMATH DE number 7536113 (Why is no real title available?)
- Constraint relaxation may be perfect
- A new tractable class of constraint satisfaction problems
- Fanout limitations on constraint systems
- Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
- Hybrid tractable classes of constraint problems
- Galois connections for patterns: an algebra of labelled graphs
- scientific article; zbMATH DE number 140384 (Why is no real title available?)
- On minimal constraint networks
- Tractable constraints on ordered domains
- Program Development in Computational Logic
- The complexity of soft constraint satisfaction
- Half-integrality, LP-branching, and FPT algorithms
- scientific article; zbMATH DE number 2243365 (Why is no real title available?)
- Periodic constraint satisfaction problems: polynomial-time algorithms
- Reduction operations in fuzzy or valued constraint satisfaction
- Placement Inference for a Client-Server Calculus
- New schemes for simplifying binary constraint satisfaction problems
- Building tractable disjunctive constraints
- On tree-preserving constraints
- Disjunctions, independence, refinements
- Parameterized complexity results in symmetry breaking
- Principles and Practice of Constraint Programming – CP 2004
- The Polytope of Tree-Structured Binary Constraint Satisfaction Problems
- scientific article; zbMATH DE number 2080302 (Why is no real title available?)
- scientific article; zbMATH DE number 2080305 (Why is no real title available?)
- Tractable decision for a constraint language implies tractable search
- Tractability by approximating constraint languages
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Periodic constraint satisfaction problems: Tractable subclasses
- Constraint satisfaction -- algorithms and complexity analysis
- Uncovering trees in constraint networks
This page was built for publication: Characterising tractable constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1321064)
