A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula

DOI10.1016/0020-0190(92)90199-6zbMath0763.68033OpenAlexW1985141379MaRDI QIDQ1199880

Zhi-Zhong Chen

Publication date: 17 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90199-6

zbMATH Keywords

satisfiabilityEREW PRAMCRCW PRAM2-CNF

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Related Items (2)

An efficiently solvable graph partition problem to which many problems are reducible ⋮ On 2-QBF truth testing in parallel

Cites Work

• An improved parallel algorithm that computes the BFS numbering of a directed graph
• A fast parallel algorithm for the maximal independent set problem
• Unnamed Item

This page was built for publication: A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula