Fast Counting with Bounded Treewidth

DOI10.1007/978-3-540-89439-1_31MaRDI QIDQ5505573zbMATH OpenOpenAlexFDO

Authors Michael Jakl, Reinhard Pichler, Stefan Rümmele, Stefan Woltran

Publication date 27 January 2009

Published in Logic for Programming, Artificial Intelligence, and Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-89439-1_31

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

Recommendations

• Counting and Enumeration Problems with Bounded Treewidth
• On treewidth approximations
• A faster tree-decomposition based algorithm for counting linear extensions
• A faster tree-decomposition based algorithm for counting linear extensions
• Efficient counting of square substrings in a tree
• Efficient counting of square substrings in a tree
• On Exact Algorithms for Treewidth
• Approximation algorithms for treewidth
• Exploiting Database Management Systems and Treewidth for Counting
• Treewidth computations. I: Upper bounds

Cited in

(10)

• Exploiting treewidth for projected model counting and its limits
• Efficient counting of square substrings in a tree
• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• Treewidth and counting projected answer sets
• Probabilistic inference and monadic second order logic
• Monadic Datalog over finite structures of bounded treewidth
• Counting and Enumeration Problems with Bounded Treewidth
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Treewidth in non-ground answer set solving and alliance problems in graphs
• Exploiting Database Management Systems and Treewidth for Counting

This page was built for publication: Fast Counting with Bounded Treewidth

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