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

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: All roads lead to Rome - New search methods for the optimal triangulation problem Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	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. 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. (en)
Title	All roads lead to Rome - New search methods for the optimal triangulation problem All roads lead to Rome - New search methods for the optimal triangulation problem (en)
skos:prefLabel	All roads lead to Rome - New search methods for the optimal triangulation problem All roads lead to Rome - New search methods for the optimal triangulation problem (en)
skos:notation	RIV/67985556:_____/12:00384920!RIV13-MSM-67985556
http://linked.open...avai/predkladatel	Ústav teorie informace a automatizace AV ČR, v. v. i.
http://linked.open...avai/riv/aktivita	I P
http://linked.open...avai/riv/aktivity	I, P(1M0572), P(GA201/09/1891), P(GEICC/08/E010)
http://linked.open...iv/cisloPeriodika	9
http://linked.open...vai/riv/dodaniDat	2013
http://linked.open...aciTvurceVysledku	Vomlel, Jiří
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Ústav teorie informace a automatizace AV ČR, v. v. i.
http://linked.open...dnocenehoVysledku	121697
http://linked.open...ai/riv/idVysledku	RIV/67985556:_____/12:00384920
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Bayesian networks; Optimal triangulation; Probabilistic inference; Cliques in a graph (en)
http://linked.open.../riv/klicoveSlovo	Cliques in a graph Optimal triangulation Probabilistic inference Bayesian networks
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[03A783E52ABA]
http://linked.open...i/riv/nazevZdroje	International Journal of Approximate Reasoning
http://linked.open...in/vavai/riv/obor	BD
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Data, algorithms, decision making Multidimensional Models of Uncertainty The logic of causal and probabilistic reasoning in uncertain environments
http://linked.open...UplatneniVysledku	2012
http://linked.open...v/svazekPeriodika	53
http://linked.open...iv/tvurceVysledku	Vomlel, Jiří Ottosen, T. J.
http://linked.open...ain/vavai/riv/wos	000311461700005
issn	0888-613X
number of pages	17 (xsd:int)
http://bibframe.org/vocab/doi	10.1016/j.ijar.2012.06.006
is http://linked.open...avai/riv/vysledek of	All roads lead to Rome - New search methods for the optimal triangulation problem

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software