Pre-processing for Triangulation of Probabilistic Networks

Please always quote using this URN: urn:nbn:de:0297-zib-6655
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Hans L. Bodlaender, Arie M.C.A. Koster, Frank van den Eijkhof, Linda C. van der Gaag
Document Type:ZIB-Report
Tag:pre-processing; probabilistic networks; treewidth; triangulation
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C85 Graph algorithms [See also 68R10, 68W05]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Rxx Discrete mathematics in relation to computer science / 68R10 Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Txx Artificial intelligence / 68T37 Reasoning under uncertainty
Date of first Publication:2001/12/14
Series (Serial Number):ZIB-Report (01-39)
Published in: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