Fast Counting with Bounded Treewidth

DOI10.1007/978-3-540-89439-1_31zbMATH Open1182.68278OpenAlexW2111738185MaRDI QIDQ5505573FDOQ5505573

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

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

Mathematics Subject Classification ID

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

Cited In (10)

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

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)