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].
Titolo: | Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network | |
Autori: | ||
Data di pubblicazione: | 2010 | |
Rivista: | ||
Citazione: | 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]. | |
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. | |
Handle: | http://hdl.handle.net/11590/142315 | |
Appare nelle tipologie: | 1.1 Articolo in rivista |