Počet záznamů: 1  

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

  1. 1.
    SYSNO ASEP0384920
    Druh ASEPJ - Článek v odborném periodiku
    Zařazení RIVJ - Článek v odborném periodiku
    Poddruh JČlánek ve WOS
    NázevAll roads lead to Rome - New search methods for the optimal triangulation problem
    Tvůrce(i) Ottosen, T. J. (DK)
    Vomlel, Jiří (UTIA-B) RID, ORCID
    Celkový počet autorů2
    Zdroj.dok.International Journal of Approximate Reasoning. - : Elsevier - ISSN 0888-613X
    Roč. 53, č. 9 (2012), s. 1350-1366
    Poč.str.17 s.
    Forma vydáníWWW - WWW
    Jazyk dok.eng - angličtina
    Země vyd.US - Spojené státy americké
    Klíč. slovaBayesian networks ; Optimal triangulation ; Probabilistic inference ; Cliques in a graph
    Vědní obor RIVBD - Teorie informace
    CEP1M0572 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í podporaUTIA-B - RVO:67985556
    UT WOS000311461700005
    DOI10.1016/j.ijar.2012.06.006
    AnotaceTo 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
    KontaktMarkéta Votavová, votavova@utia.cas.cz, Tel.: 266 052 201.
    Rok sběru2013
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.