Sum-of-Products with Default Values: Algorithms and Complexity Results

DOI10.1613/JAIR.1.12370OpenAlexW4225663447MaRDI QIDQ5076308FDOQ5076308

Authors: Robert Ganian, Eun Jung Kim, Friedrich Slivovsky, Stefan Szeider 

Publication date: 16 May 2022

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1613/jair.1.12370

Recommendations

• Approximate Counting CSP Seen from the Other Side
• scientific article; zbMATH DE number 7561704
• The Complexity of Weighted Boolean #CSP
• Constraint satisfaction with bounded treewidth revisited
• Constraint Satisfaction with Bounded Treewidth Revisited

zbMATH Keywords

constraint satisfactionsatisfiability

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Cites Work

• Fundamentals of parameterized complexity
• Algorithms for propositional model counting
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Parametrized complexity theory.
• Parameterized algorithms
• Title not available (Why is that?)
• Conjunctive-query containment and constraint satisfaction
• Constraint satisfaction with succinctly specified relations
• The complexity of soft constraint satisfaction
• Tractability in constraint satisfaction problems: a survey
• Constraint satisfaction with bounded treewidth revisited
• Treewidth. Computations and approximations
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Strong computational lower bounds via parameterized complexity
• Model counting for CNF formulas of bounded modular treewidth
• Solving \#SAT and Bayesian inference with backtracking search
• Bucket elimination: A unifying framework for reasoning
• Bayesian reasoning and machine learning.
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• A \(c^k n\) 5-approximation algorithm for treewidth
• Unifying tree decompositions for reasoning in graphical models
• Understanding model counting for \(\beta\)-acyclic CNF-formulas
• Graph-Theoretic Concepts in Computer Science
• Solving #SAT and MAXSAT by Dynamic Programming
• Model counting for formulas of bounded clique-width

Cited In (1)

• Semiring reasoning frameworks in AI and their computational complexity

This page was built for publication: Sum-of-Products with Default Values: Algorithms and Complexity Results

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