0330016 20240111140726.320091005235959.9 10 s. www cav_un_epca*0333753978-80-245-1543-4251-260PrahaUniversity of Economics2009KroupaTomášVejnarováJiřina Bayesian networks bipartite graphs graph triangulation cav_un_auth*0101228 Vomlel Jiří UTIA-B Department of Decision Making Theory Ústav teorie informace a automatizace AV ČR, v. v. i. cav_un_auth*0100825 Savický Petr UIVT-O Department of Theoretical Computer Science Ústav informatiky AV ČR, v. v. i. pdf http://library.utia.cas.cz/separaty/2009/MTR/vomlel-an experimental comparison of triangulation heuristics on transformed bn2o networks.pdf 1M0572 GA MŠk cav_un_auth*0001814 1M0545 GA MŠk CZ cav_un_auth*0203502 1ET100300517 GA AV ČR cav_un_auth*0001446 GA201/09/1891 GA ČR cav_un_auth*0253175 GEICC/08/E010 GA ČR cav_un_auth*0241637 2C06019 GA MŠk CZ cav_un_auth*0216518 CEZ:AV0Z10750506 CEZ:AV0Z10300504 In this paper we present results of experimental comparisons of several triangulation heuristics on bipartite graphs. Our motivation for testing heuristics on the family of bipartite graphs is the rank-one decomposition of BN2O networks. A BN2O network is a Bayesian network having the structure of a bipartite graph with all edges directed from the top level toward the bottom level and where all conditional probability tables are noisy-or gates. After applying the rank-one decomposition, which adds an extra level of auxiliary nodes in between the top and bottom levels, and after removing simplicial nodes of the bottom level we get so called BROD graph. This is an undirected bipartite graph. It is desirable for efficiency of the inference to find a triangulation of the BROD graph having the sum of table sizes for all cliques of the triangulated graph as small as possible. From this point of view, the minfill heuristics perform in average better than other tested heuristics (minwidth, h1, and mcs). V článku jsou prezentovány výsledky provnání různých heuristik pro triangulaci bipartitních grafů. Motivací pro testování heuristik na rodině bipartitních grafů je rozklad na tensory ranku jedna použitý na sítě typu BN2O. cav_un_auth*0254543 WUPES 2009 Liblice 19.09.2009-23.09.2009 CZ 2010 IN http://hdl.handle.net/11104/0175891 2009 pdf cav_un_epca*0333753 Proceedings of the 8th Workshop on Uncertainty Processing 978-80-245-1543-4 251 260 Praha University of Economics 2009 Kroupa Tomáš 340 Vejnarová Jiřina 340