0384920 20240111140824.120121214235959.9 000311461700005 10.1016/j.ijar.2012.06.006 17 s. WWW cav_un_epca*02567740888-613X539 (2012)1350-1366Elsevier Bayesian networks Optimal triangulation Probabilistic inference Cliques in a graph cav_un_auth*0286695 Ottosen T. J. DK cav_un_auth*0101228 Vomlel Jiří Matematická teorie rozhodování Department of Decision Making Theory MTR MTR UTIA-B Department of Decision Making Theory Ústav teorie informace a automatizace AV ČR, v. v. i. PDF soubor http://library.utia.cas.cz/separaty/2012/MTR/vomlel-all roads lead to rome - new search methods for the optimal triangulation problem.pdf 1M0572 GA MŠk cav_un_auth*0001814 2C06019 GA MŠk CZ cav_un_auth*0216518 GEICC/08/E010 GA ČR cav_un_auth*0241637 GA201/09/1891 GA ČR cav_un_auth*0253175 To perform efficient inference in Bayesian networks by means of a Junction Tree method, the network graph needs to be triangulated. The quality of this triangulation largely determines the efficiency of the subsequent inference, but the triangulation problem is unfortunately NP-hard. It is common for existing methods to use the treewidth criterion for optimality of a triangulation. However, this criterion may lead to a somewhat harder inference problem than the total table size criterion. We therefore investigate new methods for depth-first search and best-first search for finding optimal total table size triangulations. The search methods are made faster by efficient dynamic maintenance of the cliques of a graph. This problem was investigated by Stix, and in this paper we derive a new simple method based on the Bron-Kerbosch algorithm that compares favourably to Stix' approach. The new approach is generic in the sense that it can be used with other algorithms than just Bron-Kerbosch. 2013 BD 2 RVO:67985556 http://hdl.handle.net/11104/0214381 COMPUTERSCIENCEARTIFICIALINTELLIGENCE 2.165 0.447 5.5 0.00618 0.745 1920 85 1.494 Q1 65.146 70.000 Q2 Q1 2012 000311461700005 WOS PDF soubor cav_un_epca*0256774 International Journal of Approximate Reasoning 0888-613X 1873-4731 Roč. 53 č. 9 2012 1350 1366 Elsevier