Algorithms for counting 2-SAT solutions and colorings with applications

Martin Fürer, Shiva Prasad Kasiviswanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

An algorithm is presented for exactly counting the number of maximum weight satisfying assignments of a 2-CNF formula. The worst case running time of O(1.246n) for formulas with n variables improves on the previous bound of O(1.256n) by Dahllöf, Jonsson, and Wahlström. The algorithm uses only polynomial space. As a direct consequence we get an O(1.246n) time algorithm for counting maximum weighted independent sets in a graph.

Original languageEnglish (US)
Title of host publicationAlgorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings
PublisherSpringer Verlag
Pages47-57
Number of pages11
ISBN (Print)9783540728689
DOIs
StatePublished - 2007
Event3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007 - Portland, OR, United States
Duration: Jun 6 2007Jun 8 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4508 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007
Country/TerritoryUnited States
CityPortland, OR
Period6/6/076/8/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Algorithms for counting 2-SAT solutions and colorings with applications'. Together they form a unique fingerprint.

Cite this