Pre-Processing for Triangulation of Probabilistic Networks

Hans L. Bodlaender, Arie M. C. A. Koster, Frank van den Eijkhof, Linda C. van der Gaag

UAI 2001 pp. 32-39

/uai/2001/bodlaender2001uai-pre/

Abstract

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. The 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 pre-processing; for other networks, huge reductions in size are obtained.

UAI Semantic Scholar

Cite

Text

Bodlaender et al. "Pre-Processing for Triangulation of Probabilistic Networks." Conference on Uncertainty in Artificial Intelligence, 2001.

Markdown

[Bodlaender et al. "Pre-Processing for Triangulation of Probabilistic Networks." Conference on Uncertainty in Artificial Intelligence, 2001.](https://mlanthology.org/uai/2001/bodlaender2001uai-pre/)

BibTeX

@inproceedings{bodlaender2001uai-pre,
  title     = {{Pre-Processing for Triangulation of Probabilistic Networks}},
  author    = {Bodlaender, Hans L. and Koster, Arie M. C. A. and van den Eijkhof, Frank and van der Gaag, Linda C.},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year      = {2001},
  pages     = {32-39},
  url       = {https://mlanthology.org/uai/2001/bodlaender2001uai-pre/}
}