Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering

DOI10.1016/J.ARTINT.2006.09.003zbMath1130.68096OpenAlexW2156243160MaRDI QIDQ2457595

Ole J. Mengshoel, David C. Wilkins, Dan Roth

Publication date: 23 October 2007

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

Full work available at URL: https://doi.org/10.1016/j.artint.2006.09.003

zbMATH Keywords

Bayesian networksrandom generationprobabilistic reasoning\(C/V\)-ratiocontrolled experimentsmaximal clique sizetree clustering inference

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Graph theory (including graph drawing) in computer science (68R10) Knowledge representation (68T30) Reasoning under uncertainty in the context of artificial intelligence (68T37)

Related Items (5)

Evaluating topological ordering in directed acyclic graphs ⋮ Understanding the role of noise in stochastic local search: analysis and experiments ⋮ Portfolios in stochastic local search: efficiently computing most probable explanations in Bayesian networks ⋮ Mendelian error detection in complex pedigrees using weighted constraint satisfaction tech\-niques ⋮ Understanding the scalability of Bayesian network inference using clique tree growth curves

Uses Software

• HUGIN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic inference in multiply connected belief networks using loop cutsets
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Network-based heuristics for constraint-satisfaction problems
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Hamilton cycles in regular 2-connected graphs
• Approximating MAPs for belief networks is NP-hard and other theorems
• Efficient inference in Bayes networks as a combinatorial optimization problem
• Finding MAPs for belief networks is NP-hard
• Inference in belief networks: A procedural guide
• Bucket elimination: A unifying framework for reasoning
• Portfolios in stochastic local search: efficiently computing most probable explanations in Bayesian networks
• Contribution to nonserial dynamic programming
• The computational complexity of probabilistic inference using Bayesian belief networks
• On the hardness of approximate reasoning
• Local conditioning in Bayesian networks
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Improved low-density parity-check codes using irregular graphs
• The distribution of loop lengths in graphical models for turbo decoding
• An algebra of bayesian belief universes for knowledge‐based systems
• Some Theorems on Abstract Graphs
• Topological parameters for time-space tradeoff
• Recursive conditioning
• A general scheme for automatic generation of search heuristics from specification \(dependencies^{*}\)

This page was built for publication: Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering