Safe reduction rules for weighted treewidth

Please always quote using this URN: urn:nbn:de:0297-zib-7164

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.

Metadaten
Author:	Frank van den Eijkhof, Hans L. Bodlaender, Arie M.C.A. Koster
Document Type:	ZIB-Report
Tag:	preprocessing; probabilistic networks; weighted treewidth
MSC-Classification:	05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C85 Graph algorithms [See also 68R10, 68W05]
	68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Rxx Discrete mathematics in relation to computer science / 68R10 Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
	68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Txx Artificial intelligence / 68T37 Reasoning under uncertainty
Date of first Publication:	2002/12/17
Series (Serial Number):	ZIB-Report (02-49)
ZIB-Reportnumber:	02-49
Published in:	Appeared in: Algorithmica 47:2 (2007) 139-158

Open Access