Treewidth and the Computational Complexity of MAP Approximations

DOI10.1007/978-3-319-11433-0_18MaRDI QIDQ2938412zbMATH OpenOpenAlexFDO

Authors Johan Kwisthout

Publication date 14 January 2015

Published in Probabilistic Graphical Models (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-11433-0_18

Mathematics Subject Classification ID

Probabilistic graphical models (62H22) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On treewidth approximations
• Approximation algorithms for treewidth
• Treewidth: Characterizations, Applications, and Computations
• On treewidth approximations.
• Treewidth computations. II. Lower bounds
• On the complexity of computing treebreadth
• On the complexity of computing treebreadth
• Tree-width in algebraic complexity
• On Exact Algorithms for Treewidth
• On exact algorithms for treewidth

Cited in

(9)

• The complexity of approximating MAPs for belief networks with bounded probabilities
• Maximum likelihood bounded tree-width Markov networks
• On treewidth approximations
• Tree-width and the computational complexity of MAP approximations in Bayesian networks
• The necessity of bounded treewidth for efficient inference in Bayesian networks
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Inapproximability of treewidth and related problems
• scientific article; zbMATH DE number 2243356 (Why is no real title available?)
• Approximate Turing Kernelization for Problems Parameterized by Treewidth

This page was built for publication: Treewidth and the Computational Complexity of MAP Approximations

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