On approximability of propositional model counting

Cites work

A faster algorithm for propositional model counting parameterized by incidence treewidth
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
A single-exponential time 2-approximation algorithm for treewidth
Algorithmic lower bounds for problems parameterized by clique-width
Algorithms for propositional model counting
Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
Exploiting treewidth for projected model counting and its limits
scientific article; zbMATH DE number 7788352 (Why is no real title available?)
Known algorithms for edge clique cover are probably optimal
Known algorithms on graphs of bounded treewidth are probably optimal
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
Maximum minimal vertex cover parameterized by vertex cover
Model counting of monotone conjunctive normal form formulas with spectra
On problems as hard as CNF-SAT
On the complexity of k-SAT
On the computational hardness based on linear fpt-reductions
On the hardness of approximate reasoning
On the possibility of faster \textsc{SAT} algorithms
Parameterized algorithms
PP is as Hard as the Polynomial-Time Hierarchy
Scalable approximation of quantitative information flow in programs
SETH-based lower bounds for subset sum and bicriteria path
SOFSEM 2005: Theory and Practice of Computer Science
Strong computational lower bounds via parameterized complexity
The Complexity of Enumeration and Reliability Problems
Theory and Applications of Satisfiability Testing
Tinted, detached, and lazy CNF-XOR solving and its applications to counting and sampling
Treewidth: computational experiments
Treewidth. Computations and approximations
Which problems have strongly exponential complexity?

This page was built for publication: On approximability of propositional model counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7240317)