665
eng
reportzib
0
2001-12-14
2001-12-14
--
Pre-processing for Triangulation of Probabilistic Networks
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.
01-39
666
urn:nbn:de:0297-zib-6655
An extended vers. appeared in: Computational Intelligence 21:3 (2005) 286-305. Appeared in: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, J. Breese and D. Koller Eds., (2001), pp. 32-39, Published by Morgan Kaufmann Publishers, San Francisco
Hans L. Bodlaender
Arie M.C.A. Koster
Frank van den Eijkhof
Linda C. van der Gaag
ZIB-Report
01-39
eng
uncontrolled
triangulation
eng
uncontrolled
treewidth
eng
uncontrolled
probabilistic networks
eng
uncontrolled
pre-processing
Informatik, Informationswissenschaft, allgemeine Werke
Graph algorithms [See also 68R10, 68W05]
Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
Reasoning under uncertainty
ZIB Allgemein
https://opus4.kobv.de/opus4-zib/files/665/ZR-01-39.ps
https://opus4.kobv.de/opus4-zib/files/665/ZR-01-39.pdf
716
eng
reportzib
0
2002-12-17
2002-12-17
--
Safe reduction rules for weighted treewidth
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.
02-49
717
urn:nbn:de:0297-zib-7164
Appeared in: Algorithmica 47:2 (2007) 139-158
Frank van den Eijkhof
Hans L. Bodlaender
Arie M.C.A. Koster
ZIB-Report
02-49
eng
uncontrolled
weighted treewidth
eng
uncontrolled
preprocessing
eng
uncontrolled
probabilistic networks
Informatik, Informationswissenschaft, allgemeine Werke
Graph algorithms [See also 68R10, 68W05]
Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
Reasoning under uncertainty
ZIB Allgemein
NWO-TACO
https://opus4.kobv.de/opus4-zib/files/716/ZR-02-49.ps
https://opus4.kobv.de/opus4-zib/files/716/ZR-02-49.pdf