Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks

DOI10.1016/S0004-3702(03)00110-3zbMATH Open1082.68837DBLPjournals/ai/ShimonyD03OpenAlexW2029891923WikidataQ57518782 ScholiaQ57518782MaRDI QIDQ814531FDOQ814531

Carmel Domshlak, Solomon E. Shimony

Publication date: 7 February 2006

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

Full work available at URL: https://doi.org/10.1016/s0004-3702(03)00110-3

Recommendations

• Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing
• Most probable explanations in Bayesian networks: complexity and tractability
• The complexity of finding \(k\)th most probable explanations in probabilistic networks
• scientific article; zbMATH DE number 1043982
• Reasoning with BKBs -- algorithms and complexity

zbMATH Keywords

ComplexityBayes networksProbabilistic reasoningSingly-connected DAGs

Mathematics Subject Classification ID

Reasoning under uncertainty in the context of artificial intelligence (68T37)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the hardness of approximate reasoning
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• Finding MAPs for belief networks is NP-hard
• NP is as easy as detecting unique solutions
• An \(O(|V|^2)\) algorithm for single connectedness
• Probabilistic Horn abduction and Bayesian networks
• The computational complexity of probabilistic inference using Bayesian belief networks
• Title not available (Why is that?)
• Recursive conditioning
• Title not available (Why is that?)
• Approximating MAPs for belief networks is NP-hard and other theorems
• A Probabilistic Causal Model for Diagnostic Problem Solving Part I: Integrating Symbolic Causal Inference with Numeric Probabilistic Inference
• An algebra of bayesian belief universes for knowledge‐based systems
• Local conditioning in Bayesian networks
• Probabilistic conflicts in a search algorithm for estimating posterior probabilities in Bayesian networks

Cited In (6)

• Estimating the probability of meeting a deadline in schedules and plans
• Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing
• Approximate belief updating in max-2-connected Bayes networks is NP-hard
• The complexity of finding \(k\)th most probable explanations in probabilistic networks
• Approximate inference in Bayesian networks: parameterized complexity results
• A machine learning approach to algorithm selection for \(\mathcal{NP}\)-hard optimization problems: a case study on the MPE problem

This page was built for publication: Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks

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