This paper presents non-random algorithms for approximate computation in Ba
yesian networks. They are based on the use of probability trees to represen
t probability potentials, using the Kullback-Leibler cross entropy as a mea
sure of the error of the approximation. Different alternatives are presente
d and tested in several experiments with difficult propagation problems. Th
e results show how it is possible to find good approximations in short time
compared with Hugin algorithm. (C) 2000 John Wiley & Sons, Inc.