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.
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. |
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 |