Algorithms for Counting 2-Sat Solutions and Colorings with Applications

DOI10.1007/978-3-540-72870-2_5zbMath1137.68620OpenAlexW2123864423WikidataQ56288404 ScholiaQ56288404MaRDI QIDQ5434422

Shiva Prasad Kasiviswanathan, Martin Fuerer

Publication date: 4 January 2008

Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-72870-2_5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items (11)

Counting Maximal Independent Sets in Subcubic Graphs ⋮ A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ Fast algorithms for max independent set ⋮ On independent sets and bicliques in graphs ⋮ Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract) ⋮ Rényi entropies as a measure of the complexity of counting problems ⋮ A new distributed approximation algorithm for the maximum weight independent set problem ⋮ On two techniques of combining branching and treewidth ⋮ Faster graph coloring in polynomial space ⋮ Exact algorithms for counting 3-colorings of graphs

This page was built for publication: Algorithms for Counting 2-Sat Solutions and Colorings with Applications