Number of the records: 1
All roads lead to Rome - New search methods for the optimal triangulation problem
- 1.
SYSNO ASEP 0384920 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title All roads lead to Rome - New search methods for the optimal triangulation problem Author(s) Ottosen, T. J. (DK)
Vomlel, Jiří (UTIA-B) RID, ORCIDNumber of authors 2 Source Title International Journal of Approximate Reasoning. - : Elsevier - ISSN 0888-613X
Roč. 53, č. 9 (2012), s. 1350-1366Number of pages 17 s. Publication form WWW - WWW Language eng - English Country US - United States Keywords Bayesian networks ; Optimal triangulation ; Probabilistic inference ; Cliques in a graph Subject RIV BD - Theory of Information R&D Projects 1M0572 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) GEICC/08/E010 GA ČR - Czech Science Foundation (CSF) GA201/09/1891 GA ČR - Czech Science Foundation (CSF) Institutional support UTIA-B - RVO:67985556 UT WOS 000311461700005 DOI 10.1016/j.ijar.2012.06.006 Annotation 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. Workplace Institute of Information Theory and Automation Contact Markéta Votavová, votavova@utia.cas.cz, Tel.: 266 052 201. Year of Publishing 2013
Number of the records: 1