A Hybrid Algorithm to Compute Marginal and Joint Beliefs in Bayesian
  Networks and Its Complexity
  There exist two general forms of exact algorithms for updating probabilities
in Bayesian Networks. The first approach involves using a structure, usually a
clique tree, and performing local message based calculation to extract the
belief in each variable. The second general class of algorithm involves the use
of non-serial dynamic programming techniques to extract the belief in some
desired group of variables. In this paper we present a hybrid algorithm based
on the latter approach yet possessing the ability to retrieve the belief in all
single variables. The technique is advantageous in that it saves a NP-hard
computation step over using one algorithm of each type. Furthermore, this
technique re-enforces a conjecture of Jensen and Jensen [JJ94] in that it still
requires a single NP-hard step to set up the structure on which inference is
performed, as we show by confirming Li and D'Ambrosio's [LD94] conjectured
NP-hardness of OFP.
