|
|||||
|
|
Safe Reduction Rules for Weighted Treewidth |
|
| Authors: | Frank van den Eijkhof Hans L Bodlaender MCA Koster |
| Affiliation: | (1) Department of Methodology and Statistics, Faculty of Social Sciences, Utrecht University, P.O. Box 80.0140, 3508 TC, Utrecht, The Netherlands;(2) Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, The Netherlands;(3) Zuse Institute Berlin (ZIB), Takustrasse 7, D-14195, Berlin-Dahlem, Germany |
| Abstract: | Several sets of reductions rules are known for preprocessing a graph when computing its treewidth. In this paper we give reduction rules for a weighted variant of treewidth, motivated by the analysis of algorithms for probabilistic networks. We present two general reduction rules that are safe for weighted treewidth. They generalise many of the existing reduction rules for treewidth. Experimental results show that these reduction rules can significantly reduce the problem size for several instances of real-life probabilistic networks. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |