Tractability in constraint satisfaction problems: a survey (Q271997): Difference between revisions

@@ Property / Mathematics Subject Classification ID @@
+C60
@@ Property / Mathematics Subject Classification ID: 90C60 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C30
@@ Property / Mathematics Subject Classification ID: 90C30 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6570964
@@ Property / zbMATH DE Number: 6570964 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+computational complexity
@@ Property / zbMATH Keywords: computational complexity / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+polynomial-time
@@ Property / zbMATH Keywords: polynomial-time / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+dichotomy
@@ Property / zbMATH Keywords: dichotomy / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+tractable language
@@ Property / zbMATH Keywords: tractable language / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+polymorphism
@@ Property / zbMATH Keywords: polymorphism / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+microstructure
@@ Property / zbMATH Keywords: microstructure / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+forbidden pattern
@@ Property / zbMATH Keywords: forbidden pattern / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+relaxation
@@ Property / zbMATH Keywords: relaxation / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+DARN!
@@ Property / describes a project that uses: DARN! / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+ToulBar2
@@ Property / describes a project that uses: ToulBar2 / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1009693448
@@ Property / OpenAlex ID: W1009693448 / rank @@
+Normal rank
@@ Property / cites work @@
+Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
+Normal rank
@@ Property / cites work @@
+Hypertree width and related hypergraph invariants
@@ Property / cites work: Hypertree width and related hypergraph invariants / rank @@
+Normal rank
@@ Property / cites work @@
+Maintaining knowledge about temporal intervals
@@ Property / cites work: Maintaining knowledge about temporal intervals / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
+Normal rank
@@ Property / cites work @@
+Complexity of Finding Embeddings in a <i>k</i>-Tree
+Normal rank
@@ Property / cites work @@
+Finitely Related Algebras In Congruence Distributive Varieties Have Near Unanimity Terms
+Normal rank
@@ Property / cites work @@
+The collapse of the bounded width hierarchy
@@ Property / cites work: The collapse of the bounded width hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Constraint Satisfaction Problems Solvable by Local Consistency Methods
+Normal rank
@@ Property / cites work @@
+The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
+Normal rank
@@ Property / cites work @@
+On the minimality and global consistency of row-convex constraint networks
+Normal rank
@@ Property / cites work @@
+Constraint tightness and looseness versus local and global consistency
+Normal rank
@@ Property / cites work @@
+Nonserial dynamic programming
@@ Property / cites work: Nonserial dynamic programming / rank @@
+Normal rank
@@ Property / cites work @@
+Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
+Normal rank
@@ Property / cites work @@
+Relatively quantified constraint satisfaction
@@ Property / cites work: Relatively quantified constraint satisfaction / rank @@
+Normal rank
@@ Property / cites work @@
+Maximal infinite-valued constraint languages
@@ Property / cites work: Maximal infinite-valued constraint languages / rank @@
+Normal rank
@@ Property / cites work @@
+Non-dichotomies in Constraint Satisfaction Complexity
+Normal rank
@@ Property / cites work @@
+The complexity of equality constraint languages
@@ Property / cites work: The complexity of equality constraint languages / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of temporal constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
+Normal rank
@@ Property / cites work @@
+Combinatorial problems raised from 2-semilattices
@@ Property / cites work: Combinatorial problems raised from 2-semilattices / rank @@
+Normal rank
@@ Property / cites work @@
+A dichotomy theorem for constraint satisfaction problems on a 3-element set
+Normal rank
@@ Property / cites work @@
+Constraint Satisfaction Parameterized by Solution Size
+Normal rank
@@ Property / cites work @@
+Complexity of conservative constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+The complexity of the counting constraint satisfaction problem
+Normal rank
@@ Property / cites work @@
+Conservative constraint satisfaction re-revisited
@@ Property / cites work: Conservative constraint satisfaction re-revisited / rank @@
+Normal rank
@@ Property / cites work @@
+A Simple Algorithm for Mal'tsev Constraints
@@ Property / cites work: A Simple Algorithm for Mal'tsev Constraints / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of weighted Boolean \#CSP with mixed signs
+Normal rank
@@ Property / cites work @@
+The expressibility of functions on the boolean domain, with applications to counting CSPs
+Normal rank
@@ Property / cites work @@
+A unifying approach to temporal constraint reasoning
+Normal rank
@@ Property / cites work @@
+Classifying the Complexity of Constraints Using Finite Algebras
+Normal rank
@@ Property / cites work @@
+The complexity of maximal constraint languages
@@ Property / cites work: The complexity of maximal constraint languages / rank @@
+Normal rank
@@ Property / cites work @@
+Dualities for Constraint Satisfaction Problems
@@ Property / cites work: Dualities for Constraint Satisfaction Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Recent Results on the Algebraic Approach to the CSP
+Normal rank
@@ Property / cites work @@
+Closure properties of constraints
@@ Property / cites work: Closure properties of constraints / rank @@
+Normal rank
@@ Property / cites work @@
+On Maltsev Digraphs
@@ Property / cites work: On Maltsev Digraphs / rank @@
+Normal rank
@@ Property / cites work @@
+An Algebraic Theory of Complexity for Discrete Optimization
+Normal rank
@@ Property / cites work @@
+Arc consistency and friends
@@ Property / cites work: Arc consistency and friends / rank @@
+Normal rank
@@ Property / cites work @@
+Constraint satisfaction with succinctly specified relations
+Normal rank
@@ Property / cites work @@
+Improved upper bounds for vertex cover
@@ Property / cites work: Improved upper bounds for vertex cover / rank @@
+Normal rank
@@ Property / cites work @@
+Recognizing Berge graphs
@@ Property / cites work: Recognizing Berge graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The strong perfect graph theorem
@@ Property / cites work: The strong perfect graph theorem / rank @@
+Normal rank
@@ Property / cites work @@
+The ellipsoid method and its consequences in combinatorial optimization
+Normal rank
@@ Property / cites work @@
+The Tractability of CSP Classes Defined by Forbidden Patterns
+Normal rank
@@ Property / cites work @@
+The complexity of homomorphism and constraint satisfaction problems seen from the other side
+Normal rank
@@ Property / cites work @@
+The complexity of soft constraint satisfaction
@@ Property / cites work: The complexity of soft constraint satisfaction / rank @@
+Normal rank
@@ Property / cites work @@
+Building tractable disjunctive constraints
@@ Property / cites work: Building tractable disjunctive constraints / rank @@
+Normal rank
@@ Property / cites work @@
+Hypertree decompositions and tractable queries
@@ Property / cites work: Hypertree decompositions and tractable queries / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of theorem-proving procedures
@@ Property / cites work: The complexity of theorem-proving procedures / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-time algorithms for testing the realisability of line drawings of curved objects
+Normal rank
@@ Property / cites work @@
+Characterising tractable constraints
@@ Property / cites work: Characterising tractable constraints / rank @@
+Normal rank
@@ Property / cites work @@
+Paths, Trees, and Flowers
@@ Property / cites work: Paths, Trees, and Flowers / rank @@
+Normal rank
@@ Property / cites work @@
+Soft arc consistency revisited
@@ Property / cites work: Soft arc consistency revisited / rank @@
+Normal rank
@@ Property / cites work @@
+Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
+Normal rank
@@ Property / cites work @@
+Monotone Temporal Planning: Tractability, Extensions and Applications
+Normal rank
@@ Property / cites work @@
+Network-based heuristics for constraint-satisfaction problems
+Normal rank
@@ Property / cites work @@
+Hybrid tractability of valued constraint problems
@@ Property / cites work: Hybrid tractability of valued constraint problems / rank @@
+Normal rank
@@ Property / cites work @@
+Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
+Normal rank
@@ Property / cites work @@
+Q4385531
@@ Property / cites work: Q4385531 / rank @@
+Normal rank
@@ Property / cites work @@
+On generating all solutions of generalized satisfiability problems
+Normal rank
@@ Property / cites work @@
+Complexity of constraints. An overview of current research themes
+Normal rank
@@ Property / cites work @@
+A new tractable class of constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+Generalized Majority-Minority Operations are Tractable
+Normal rank
@@ Property / cites work @@
+Q4495111
@@ Property / cites work: Q4495111 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4386933
@@ Property / cites work: Q4386933 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Subexponential-Time Complexity of CSP
@@ Property / cites work: On the Subexponential-Time Complexity of CSP / rank @@
+Normal rank
@@ Property / cites work @@
+From local to global consistency
@@ Property / cites work: From local to global consistency / rank @@
+Normal rank
@@ Property / cites work @@
+Temporal constraint networks
@@ Property / cites work: Temporal constraint networks / rank @@
+Normal rank
@@ Property / cites work @@
+Computing and Combinatorics
@@ Property / cites work: Computing and Combinatorics / rank @@
+Normal rank
@@ Property / cites work @@
+Constraint satisfaction over connected row-convex constraints
+Normal rank
@@ Property / cites work @@
+Fixed-Parameter Tractability and Completeness I: Basic Results
+Normal rank
@@ Property / cites work @@
+Q4263467
@@ Property / cites work: Q4263467 / rank @@
+Normal rank
@@ Property / cites work @@
+An Effective Dichotomy for the Counting Constraint Satisfaction Problem
+Normal rank
@@ Property / cites work @@
+The Complexity of Weighted Boolean #CSP
@@ Property / cites work: The Complexity of Weighted Boolean #CSP / rank @@
+Normal rank
@@ Property / cites work @@
+Full Constraint Satisfaction Problems
@@ Property / cites work: Full Constraint Satisfaction Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q4386965
@@ Property / cites work: Q4386965 / rank @@
+Normal rank
@@ Property / cites work @@
+The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Backdoors into heterogeneous classes of SAT and CSP
+Normal rank
@@ Property / cites work @@
+Domain permutation reduction for constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+Q2762493
@@ Property / cites work: Q2762493 / rank @@
+Normal rank
@@ Property / cites work @@
+The Structure of Tractable Constraint Satisfaction Problems
+Normal rank
@@ Property / cites work @@
+Deciding First-Order Properties of Nowhere Dense Graphs
+Normal rank
@@ Property / cites work @@
+Constraint solving via fractional edge covers
@@ Property / cites work: Constraint solving via fractional edge covers / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of H-coloring
@@ Property / cites work: On the complexity of H-coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Colouring, constraint satisfaction, and complexity
+Normal rank
@@ Property / cites work @@
+On the Computational Complexity of Monotone Constraint Satisfaction Problems
+Normal rank
@@ Property / cites work @@
+Tractability and Learnability Arising from Algebras with Few Subpowers
+Normal rank
@@ Property / cites work @@
+Q4633938
@@ Property / cites work: Q4633938 / rank @@
+Normal rank
@@ Property / cites work @@
+Local Consistency and SAT-Solvers
@@ Property / cites work: Local Consistency and SAT-Solvers / rank @@
+Normal rank
@@ Property / cites work @@
+On the algebraic structure of combinatorial problems
+Normal rank
@@ Property / cites work @@
+Constraints, consistency and closure
@@ Property / cites work: Constraints, consistency and closure / rank @@
+Normal rank
@@ Property / cites work @@
+Tractable constraints on ordered domains
@@ Property / cites work: Tractable constraints on ordered domains / rank @@
+Normal rank
@@ Property / cites work @@
+Q3365840
@@ Property / cites work: Q3365840 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / rank @@
+Normal rank
@@ Property / cites work @@
+CSP for binary conservative relational structures
@@ Property / cites work: CSP for binary conservative relational structures / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of General-Valued CSPs
@@ Property / cites work: The Complexity of General-Valued CSPs / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of conservative valued CSPs
@@ Property / cites work: The complexity of conservative valued CSPs / rank @@
+Normal rank
@@ Property / cites work @@
+A finite set of functions with an EXPTIME-complete composition problem
+Normal rank
@@ Property / cites work @@
+Characterizations of several Maltsev conditions.
@@ Property / cites work: Characterizations of several Maltsev conditions. / rank @@
+Normal rank
@@ Property / cites work @@
+Reasoning about temporal relations
@@ Property / cites work: Reasoning about temporal relations / rank @@
+Normal rank
@@ Property / cites work @@
+Constraint Satisfaction Problems on Intervals and Lengths
+Normal rank
@@ Property / cites work @@
+A new line of attack on the dichotomy conjecture
@@ Property / cites work: A new line of attack on the dichotomy conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+On the Structure of Polynomial Time Reducibility
@@ Property / cites work: On the Structure of Polynomial Time Reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+A Characterisation of First-Order Constraint Satisfaction Problems
+Normal rank
@@ Property / cites work @@
+TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
+Normal rank
@@ Property / cites work @@
+The Parameterized Complexity of <i>k</i>-B<scp>iclique</scp>
+Normal rank
@@ Property / cites work @@
+A Probabilistic Approach to the Dichotomy Problem
@@ Property / cites work: A Probabilistic Approach to the Dichotomy Problem / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized complexity of constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+Approximating fractional hypertree width
@@ Property / cites work: Approximating fractional hypertree width / rank @@
+Normal rank
@@ Property / cites work @@
+Tractable structures for constraint satisfaction with truth tables
+Normal rank
@@ Property / cites work @@
+Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
+Normal rank
@@ Property / cites work @@
+Satisfiability of acyclic and almost acyclic CNF formulas
+Normal rank
@@ Property / cites work @@
+Constraint satisfaction with bounded treewidth revisited
+Normal rank
@@ Property / cites work @@
+Time–dependent Simple Temporal Networks: Properties and Algorithms
+Normal rank
@@ Property / cites work @@
+Graph minors. XIII: The disjoint paths problem
@@ Property / cites work: Graph minors. XIII: The disjoint paths problem / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of satisfiability problems
@@ Property / cites work: The complexity of satisfiability problems / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
+Normal rank
@@ Property / cites work @@
+The Complexity of Finite-Valued CSPs
@@ Property / cites work: The Complexity of Finite-Valued CSPs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3140234
@@ Property / cites work: Q3140234 / rank @@
+Normal rank
@@ Property / cites work @@
+Certainty closure
@@ Property / cites work: Certainty closure / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Valued Constraint Satisfaction Problems
+Normal rank
@@ Property / cites work @@
+DARN! A weighted constraint solver for RNA motif localization
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:271997