Benvenuti nell'Anagrafe della Ricerca d'Ateneo
La valutazione delle attività di ricerca che si svolgono nelle università ha assunto un'importanza rilevante sia per l'intero sistema universitario sia all'interno di ogni singolo ateneo. Roma Tre si è quindi dotata di idonei strumenti informativi in grado di supportare al meglio le azioni di monitoraggio e di valutazione delle attività di ricerca svolte nei propri dipartimentied ha realizzato una Anagrafe della Ricerca di Ateneo.
EnglishIn 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 |
File in questo prodotto:
http://hdl.handle.net/11590/142315
Copyright © 2021