Recognizing frozen variables in constraint satisfaction problems
type: Item
instance of: scholarly article
title: Recognizing frozen variables in constraint satisfaction problems
zbMATH Open document ID: 1086.68056
author: Peter Jonsson
author: Andrei Krokhin
published in: Theoretical Computer Science
publication date: 2005-02-09T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 2132496
zbMATH Keywords: Constraint satisfaction
zbMATH Keywords: Frozen variable
zbMATH Keywords: Computational complexity
zbMATH Keywords: Polymorphism
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.08.006
OpenAlex ID: W1968063049
cites work: The scaling window of the 2-SAT transition
cites work: Computer Science Logic
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: Q2754150
cites work: The complexity of maximal constraint languages
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Frozen development in graph coloring
cites work: Q4737176
cites work: List homomorphisms and circular arc graphs
cites work: Bi‐arc graphs and the complexity of list homomorphisms
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
cites work: Hypertree decompositions and tractable queries
cites work: Some optimal inapproximability results
cites work: On the complexity of H-coloring
cites work: On the algebraic structure of combinatorial problems
cites work: Closure properties of constraints
cites work: How to determine the expressive power of constraints
cites work: Q4934341
cites work: Auditing Boolean attributes
cites work: Conjunctive-query containment and constraint satisfaction
cites work: Q4254883
cites work: Q4704799
cites work: Networks of constraints: Fundamental properties and applications to picture processing
cites work: Q4298260
cites work: The complexity of facets resolved
cites work: The complexity of facets (and some facets of complexity)
cites work: Q4354427
cites work: Q3208654
cites work: The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
cites work: Q3739182
cites work: The complexity of satisfiability problems
cites work: Q4488090
cites work: Q3739181
cites work: NP is as easy as detecting unique solutions
cites work: Reasoning about qualitative temporal information
DOI: 10.1016/J.TCS.2004.08.006
description: scientific article; zbMATH DE number 2132496