Filtern
Erscheinungsjahr
- 2001 (1) (entfernen)
Dokumenttyp
- ZIB-Report (1)
Sprache
- Englisch (1) (entfernen)
Volltext vorhanden
- ja (1)
Gehört zur Bibliographie
- nein (1)
Schlagworte
- pre-processing (1)
- probabilistic networks (1)
- treewidth (1)
- triangulation (1)
Institut
- ZIB Allgemein (1)
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.