Locally consistent constraint satisfaction problems

DOI10.1016/J.TCS.2005.09.012MaRDI QIDQ2581264zbMATH OpenOpenAlexWikidataFDO

Authors Zdeněk Dvořák, Daniel Král', Ondřej Pangrác

Publication date 9 January 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.09.012

zbMATH Keywords

2-SATBoolean predicatesCNF formulasconstraint satisfaction problems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Mathematical Foundations of Computer Science 2005
• Automata, Languages and Programming
• Limit Behavior of Locally Consistent Constraint Satisfaction Problems
• Graph-Theoretic Concepts in Computer Science
• Constraint Satisfaction Problems Solvable by Local Consistency Methods

Cites work

• A guided tour of Chernoff bounds
• A sharp threshold for a random constraint satisfaction problem
• A Sufficient Condition for Backtrack-Free Search
• Complexity of Partial Satisfaction
• Complexity of partial satisfaction. II.
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 1324671 (Why is no real title available?)
• scientific article; zbMATH DE number 1113991 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Implications of forbidden structures for extremal algorithmic problems
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Local and global relational consistency
• Max-Min Probabilities in the Voting Paradox
• On Local Versus Global Satisfiability
• On the Approximation of Maximum Satisfiability
• Some optimal inapproximability results
• The complexity of satisfiability problems
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Worst-case time bounds for coloring and satisfiability problems

Cited in

(7)

• Limit Behavior of Locally Consistent Constraint Satisfaction Problems
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Local classification of constraints
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
• Automata, Languages and Programming
• Mathematical Foundations of Computer Science 2005
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Locally consistent constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581264)