Počet záznamů: 1
All roads lead to Rome - New search methods for the optimal triangulation problem
- 1.
SYSNO ASEP 0384920 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název All roads lead to Rome - New search methods for the optimal triangulation problem Tvůrce(i) Ottosen, T. J. (DK)
Vomlel, Jiří (UTIA-B) RID, ORCIDCelkový počet autorů 2 Zdroj.dok. International Journal of Approximate Reasoning. - : Elsevier - ISSN 0888-613X
Roč. 53, č. 9 (2012), s. 1350-1366Poč.str. 17 s. Forma vydání WWW - WWW Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova Bayesian networks ; Optimal triangulation ; Probabilistic inference ; Cliques in a graph Vědní obor RIV BD - Teorie informace CEP 1M0572 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy GEICC/08/E010 GA ČR - Grantová agentura ČR GA201/09/1891 GA ČR - Grantová agentura ČR Institucionální podpora UTIA-B - RVO:67985556 UT WOS 000311461700005 DOI 10.1016/j.ijar.2012.06.006 Anotace 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. Pracoviště Ústav teorie informace a automatizace Kontakt Markéta Votavová, votavova@utia.cas.cz, Tel.: 266 052 201. Rok sběru 2013
Počet záznamů: 1