Model counting for CNF formulas of bounded modular treewidth
From MaRDI portal
Publication:334935
DOI10.1007/S00453-015-0030-XzbMATH Open1353.68137OpenAlexW2309930662MaRDI QIDQ334935FDOQ334935
Authors: Daniël Paulusma, Friedrich Slivovsky, Stefan Szeider 
Publication date: 1 November 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2013/3922/
Recommendations
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- The complexity of computing the permanent
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Algorithms for propositional model counting
- Handle-rewriting hypergraph grammars
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Approximating clique-width and branch-width
- Satisfiability of acyclic and almost acyclic CNF formulas
- Treewidth. Computations and approximations
- On the hardness of approximate reasoning
- Theory and Applications of Satisfiability Testing
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- A survey of the algorithmic aspects of modular decomposition
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
- Title not available (Why is that?)
- Solving \#SAT and Bayesian inference with backtracking search
- Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width
- Homomorphic hashing for sparse coefficient extraction
- Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
Cited In (13)
- The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
- Title not available (Why is that?)
- New width parameters for SAT and \#SAT
- Solving projected model counting by utilizing treewidth and its limits
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On efficiently solvable cases of quantum \(k\)-SAT
- Finer Tight Bounds for Coloring on Clique-Width
- Title not available (Why is that?)
- Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth
- Sum-of-Products with Default Values: Algorithms and Complexity Results
- Counting linear extensions: parameterizations by treewidth
This page was built for publication: Model counting for CNF formulas of bounded modular treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334935)
