TY - GEN A1 - Bodlaender, Hans L. A1 - Koster, Arie M.C.A. A1 - Eijkhof, Frank van den A1 - Gaag, Linda C. van der T1 - Pre-processing for Triangulation of Probabilistic Networks N2 - The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained. T3 - ZIB-Report - 01-39 KW - triangulation KW - treewidth KW - probabilistic networks KW - pre-processing Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6655 ER - TY - GEN A1 - Eijkhof, Frank van den A1 - Bodlaender, Hans L. A1 - Koster, Arie M.C.A. T1 - Safe reduction rules for weighted treewidth N2 - Several sets of reductions rules are known for preprocessing a graph when computing its treewidth. In this paper, we give reduction rules for a weighted variant of treewidth, motivated by the analysis of algorithms for probabilistic networks. We present two general reduction rules that are safe for weighted treewidth. They generalise many of the existing reduction rules for treewidth. Experimental results show that these reduction rules can significantly reduce the problem size for several instances of real-life probabilistic networks. T3 - ZIB-Report - 02-49 KW - weighted treewidth KW - preprocessing KW - probabilistic networks Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7164 ER -