All roads lead to Rome - New search methods for the optimal triangulation problem

0384920 - ÚTIA 2013 RIV US eng J - Journal Article
Ottosen, T. J. - Vomlel, Jiří
All roads lead to Rome - New search methods for the optimal triangulation problem.
International Journal of Approximate Reasoning. Roč. 53, č. 9 (2012), s. 1350-1366. ISSN 0888-613X. E-ISSN 1873-4731
R&D Projects: GA MŠMT 1M0572; GA ČR GEICC/08/E010; GA ČR GA201/09/1891
Grant - others:GA MŠk(CZ) 2C06019
Institutional support: RVO:67985556
Keywords : Bayesian networks * Optimal triangulation * Probabilistic inference * Cliques in a graph
Subject RIV: BD - Theory of Information
Impact factor: 1.729, year: 2012
http://library.utia.cas.cz/separaty/2012/MTR/vomlel-all roads lead to rome - new search methods for the optimal triangulation problem.pdf

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.
Permanent Link: http://hdl.handle.net/11104/0214381