Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!zaphod.mps.ohio-state.edu!ub!dsinc!netnews.upenn.edu!grad1.cis.upenn.edu!resnik
From: resnik@grad1.cis.upenn.edu (Philip Resnik)
Newsgroups: comp.theory
Subject: Seeking 2SAT algorithm
Message-ID: <27974@netnews.upenn.edu>
Date: 13 Aug 90 13:42:07 GMT
Sender: news@netnews.upenn.edu
Reply-To: resnik@grad1.cis.upenn.edu (Philip Resnik)
Distribution: usa
Organization: University of Pennsylvania
Lines: 15

Can someone please point me to a detailed description of one of the
polynomial time algorithms for 2SAT?  I know of two algorithms, one
involving resolution (mentioned in G&J) and the other involving
construction of a digraph corresponding to the expression (mentioned
in S. Baase's algorithms textbook), but have not found a detailed
discussion of either of them.

Thanks,

  Philip


resnik@grad1.cis.upenn.edu
Computer and Information Science, Moore School of Engineering
University of Pennsylvania, Philadelphia, PA 19104