Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network

In this paper we propose a simple algorithm called CLIQUEMINTRIANG for computing a minimal triangulation of a graph. If F is the set of edges that is added to G to make it a complete graph K(n) then the asymptotic complexity of CLIQUEMINTRIANG is O(vertical bar F vertical bar (delta(2) + vertical bar F vertical bar)) where delta is the degree of the subgraph of K(n) induced by F. Therefore our algorithm performs well when G is a dense graph. We also show how to exploit the existing minimal triangulation techniques in conjunction with CLIQUEMINTRIANG to efficiently find a minimal triangulation of nondense graphs. Finally we show how the algorithm can be adapted to perform a backward stepwise selection of decomposable Markov networks; the resulting procedure has the same time complexity as that of existing similar algorithms. (C) 2009 Elsevier B.V. All rights reserved.