Counting Satisfying Assignments in 2-SAT and 3-SAT
2003 (English)Conference paper (Other academic)
We present an O(1.3247n) algorithm for counting the number of satisfying assignments for instances of 2-SAT and an O(1.6894n) algorithm for instances of 3-SAT. This is an improvement compared to the previously best known algorithms running in O(1.381n) and O(1.739n) time, respectively.
Place, publisher, year, edition, pages
2003. 1-8 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 (Print) 1611-3349 (Online) ; 2387
IdentifiersURN: urn:nbn:se:liu:diva-14394DOI: 10.1007/3-540-45655-4_57ISBN: 978-3-540-43996-7OAI: oai:DiVA.org:liu-14394DiVA: diva2:23415
8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002