Triangulation of Bayesian networks by retriangulation
M. Julia Flores, José Antonio Gámez · International Journal of Intelligent Systems · 2003
Triangulation of Bayesian networks (BNs) is an NP-hard problem and of great importance for the efficiency of propagation algorithms. Several approaches, most of them basically heuristic, have been proposed to search optimal solutions for this problem. Recently, Olesen and Madsen1 launched the possibility of applying the maximal prime subgraph decomposition (MPSD) to the problem of triangulation. The idea is to retriangulate separately each MPS, so that we can work on smaller graphs. In this article, we exploit this idea by using both greedy heuristic algorithms and stochastic ones [genetic algorithms (GAs)]. From an experimentation performed over 10 real complex networks, we study empirically the usefulness of applying this MPSD-based retriangulation. © 2003 Wiley Periodicals, Inc.