To perform ecient inference in Bayesian networks, the network graph needs to be triangu-
lated. The quality of this triangulation largely determines the efficiency of the subsequent
inference, but the triangulation problem is unfortunately NP-hard. It is common for ex-
isting methods to use the treewidth criterion for optimality of a triangulation. However,
this criterion may lead to a somewhat harder inference problem than the total table size
criterion. We therefore investigate new methods for depth-first search and best-first search
for finding optimal total table size triangulations. The search methods are made faster by
eficient dynamic maintenance of the cliques of a graph. The algorithms are mainly sup-
posed to be off-line methods, but they may form the basis for ecient any-time heuristics.
Furthermore, the methods make it possible to evaluate the quality of heuristics precisely.