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 Kn then the asymptotic complexity of CliqueMinTriang is O(|F|(δ2+|F|)) where δ is the degree of the subgraph of Kn 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.

Mezzini, M., & Moscarini, M. (2010). Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network. THEORETICAL COMPUTER SCIENCE, 411(7-9), 958-966 [10.1016/j.tcs.2009.10.004].

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

MEZZINI, MAURO;
2010

Abstract

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 Kn then the asymptotic complexity of CliqueMinTriang is O(|F|(δ2+|F|)) where δ is the degree of the subgraph of Kn 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.
Mezzini, M., & Moscarini, M. (2010). Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network. THEORETICAL COMPUTER SCIENCE, 411(7-9), 958-966 [10.1016/j.tcs.2009.10.004].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/142315
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 10
social impact