|
A Linear Time Parallel Algorithm for the 2-CNF
Satisfiability Problem
El-Sayed M. EI-Horbaty
Department of Computer
Science, Faculty of Computer & Information Sciences,
Ain Shams University,
Cairo, EGYPT
E-mail: horbaty@hotmail.com
Abstract:
This paper
presents a parallel algorithm for finding a satisfying truth assignment to a
given 2-CNF-SAT problem on a tree machine model of computation.
The algorithm requires O(log2n) complexity time using a tree
machine model of computation with n leaf processing elements.
Keywords: 2-CNF-SAT, Parallel Algorithms,
Tree machines, Complexity Time
|
