Solving projected model counting by utilizing treewidth and its limits
From MaRDI portal
Publication:2680775
DOI10.1016/j.artint.2022.103810OpenAlexW4307419862MaRDI QIDQ2680775
Patrick Thier, Johannes K. Fichte, Stefan Woltran, Markus Hecher, Michael Morak
Publication date: 4 January 2023
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.artint.2022.103810
computational complexitycountinglower boundstree decompositionsparameterized algorithmsparameterized complexityexponential time hypothesisBoolean logicgraph problemsdatabase management systemsprojected model countinghybrid solvinghigh treewidthnested dynamic programming
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Clingo
- sharpSAT
- Even faster integer multiplication
- Fundamentals of parameterized complexity
- Which problems have strongly exponential complexity?
- Exploiting treewidth for projected model counting and its limits
- Practical access to dynamic programming on tree decompositions
- ProCount: weighted projected model counting with graded project-join trees
- Algorithms for propositional model counting
- Treewidth and counting projected answer sets
- Answer set solving with bounded treewidth revisited
- Positive-instance driven dynamic programming for treewidth
- Parametrized complexity theory.
- Subtractive reductions and complete problems for counting complexity classes
- Taming high treewidth with abstraction, nested dynamic programming, and database technology
- On the hardness of approximate reasoning
- Detecting inconsistencies in large biological networks with answer set programming
- Counting and Enumeration Problems with Bounded Treewidth
- Solving #SAT and MAXSAT by Dynamic Programming
- Laissez-Faire Caching for Parallel #SAT Solving
- $$\#\exists $$ SAT: Projected Model Counting
- Introduction to Information Retrieval
- Solution Enumeration for Projected Boolean Search Problems
- The Complexity of Enumeration and Reliability Problems
- Combining Treewidth and Backdoors for CSP.
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- An Experimental Study of the Treewidth of Real-World Graph Data
- Counting Answers to Existential Questions
- Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.
- DynASP2.5: Dynamic Programming on Tree Decompositions in Action
- Lower Bounds for QBFs of Bounded Treewidth
- Multi-shot ASP solving with clingo
- Implementing Efficient All Solutions SAT Solvers
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Bayesian Networks
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
This page was built for publication: Solving projected model counting by utilizing treewidth and its limits
