| bibtype |
J -
Journal Article
|
| ARLID |
0384920 |
| utime |
20240111140824.1 |
| mtime |
20121214235959.9 |
| WOS |
000311461700005 |
| DOI |
10.1016/j.ijar.2012.06.006 |
| title
(primary) (eng) |
All roads lead to Rome - New search methods for the optimal triangulation problem |
| specification |
| page_count |
17 s. |
| media_type |
WWW |
|
| serial |
| ARLID |
cav_un_epca*0256774 |
| ISSN |
0888-613X |
| title
|
International Journal of Approximate Reasoning |
| volume_id |
53 |
| volume |
9 (2012) |
| page_num |
1350-1366 |
| publisher |
|
|
| keyword |
Bayesian networks |
| keyword |
Optimal triangulation |
| keyword |
Probabilistic inference |
| keyword |
Cliques in a graph |
| author
(primary) |
| ARLID |
cav_un_auth*0286695 |
| name1 |
Ottosen |
| name2 |
T. J. |
| country |
DK |
|
| author
|
| ARLID |
cav_un_auth*0101228 |
| name1 |
Vomlel |
| name2 |
Jiří |
| full_dept (cz) |
Matematická teorie rozhodování |
| full_dept |
Department of Decision Making Theory |
| department (cz) |
MTR |
| department |
MTR |
| institution |
UTIA-B |
| full_dept |
Department of Decision Making Theory |
| fullinstit |
Ústav teorie informace a automatizace AV ČR, v. v. i. |
|
| source |
|
| cas_special |
| project |
| project_id |
1M0572 |
| agency |
GA MŠk |
| ARLID |
cav_un_auth*0001814 |
|
| project |
| project_id |
2C06019 |
| agency |
GA MŠk |
| country |
CZ |
| ARLID |
cav_un_auth*0216518 |
|
| project |
| project_id |
GEICC/08/E010 |
| agency |
GA ČR |
| ARLID |
cav_un_auth*0241637 |
|
| project |
| project_id |
GA201/09/1891 |
| agency |
GA ČR |
| ARLID |
cav_un_auth*0253175 |
|
| abstract
(eng) |
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. |
| reportyear |
2013 |
| RIV |
BD |
| num_of_auth |
2 |
| inst_support |
RVO:67985556 |
| permalink |
http://hdl.handle.net/11104/0214381 |
| mrcbT16-e |
COMPUTERSCIENCEARTIFICIALINTELLIGENCE |
| mrcbT16-f |
2.165 |
| mrcbT16-g |
0.447 |
| mrcbT16-h |
5.5 |
| mrcbT16-i |
0.00618 |
| mrcbT16-j |
0.745 |
| mrcbT16-k |
1920 |
| mrcbT16-l |
85 |
| mrcbT16-s |
1.494 |
| mrcbT16-4 |
Q1 |
| mrcbT16-B |
65.146 |
| mrcbT16-C |
70.000 |
| mrcbT16-D |
Q2 |
| mrcbT16-E |
Q1 |
| arlyear |
2012 |
| mrcbU34 |
000311461700005 WOS |
| mrcbU56 |
PDF soubor |
| mrcbU63 |
cav_un_epca*0256774 International Journal of Approximate Reasoning 0888-613X 1873-4731 Roč. 53 č. 9 2012 1350 1366 Elsevier |
|