@Article{Delcher96,
author = "Arthur L. Delcher and Adam J. Grove and
Simon Kasif and Judea Pearl",
title = "Logarithmic-time updates and queries in
probabilistic networks",
journal = "Journal of Artificial Intelligence Research",
year = 1996,
volume = 4,
month = feb,
pages = "37--59"}
Postscript or PDF can be downloaded from:
http://www.jair.org/abstracts/delcher96a.html
Also, my paper in UAI-98, "Logarithmic Time Parallel Bayesian Inference",
pp. 431-438, describes an algorithm that runs in O(log n) time for
polytree networks on a PRAM with n processors. You can download the
postscript from:
http://www.eecs.umich.edu/~dpennock/homepage/papers/parallel-final.ps
or I would be happy to mail you a copy. The potential benefit of either
algorithm for multiply connected networks is less clear.
Good luck,
--Dave