Triangulation of Graphs -- Algorithms Giving Small Total State Space

The problem of achieving small total state space for triangulated belief graphs (networks) is considered. It is an NP -complete problem to find a triangulation with minimum state space. Our interest in this topic originates from the field of knowledge engineering where the applied knowledge representation scheme is provided by the notion of causal probabilistic networks (belief networks); CPNs for short. The application of a generalised evidence propagation scheme in CPNs requires triangularity (chordality) of the actual network. The paper includes a survey and evaluation of existing triangulation algorithms most of which are found to be highly ineffective w.r.t. the applied efficiency measure. Simple heuristic methods are presented and found to produce high-quality triangulations. Moreover, we introduce a method by which any non-minimal triangulation may be turned into a minimal one. Furthermore, we present a stochastic algorithm based on a technique known as simulated annealing by wh..