Formula dissection: A parallel algorithm for constraint satisfaction

DOI10.1016/J.CAMWA.2007.07.002MaRDI QIDQ931750zbMATH OpenOpenAlexFDO

Authors J. Reif, Simon Kasif, Deepak Sherlekar

Publication date 26 June 2008

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.camwa.2007.07.002

zbMATH Keywords

graphparallel algorithmcombinatorial searchdissectionBoolean formula

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 1304346
• scientific article; zbMATH DE number 828719
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• Solving satisfiability in less than \(2^ n\) steps
• scientific article; zbMATH DE number 4039349

Cites work

• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 619541 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A Proof Procedure Using Connection Graphs
• A Separator Theorem for Planar Graphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Applications of a Planar Separator Theorem
• Consistency in networks of relations
• Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
• Hard examples for resolution
• On the Problem of Partitioning Planar Graphs
• Parallel Algorithms in Graph Theory: Planarity Testing
• Parallel concepts in graph theory
• Parallelism in random access machines
• Planar Formulae and Their Uses
• Principles of Constraint Programming
• Scene Labeling by Relaxation Operations
• The complexity of recognizing polyhedral scenes
• Using rewriting rules for connection graphs to prove theorems

Cited in

(7)

• Partitioning methods for satisfiability testing on large formulas
• A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula
• scientific article; zbMATH DE number 828719 (Why is no real title available?)
• Local consistency in parallel constraint satisfaction networks
• A tagging method for parallel constraint satisfaction
• On the constraint length of random \(k\)-CSP
• Fast and parallel decomposition of constraint satisfaction problems

This page was built for publication: Formula dissection: A parallel algorithm for constraint satisfaction

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