<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>716</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-12-17</completedDate>
    <publishedDate>2002-12-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Safe reduction rules for weighted treewidth</title>
    <abstract language="eng">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.</abstract>
    <identifier type="serial">02-49</identifier>
    <identifier type="opus3-id">717</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7164</identifier>
    <enrichment key="SourceTitle">Appeared in: Algorithmica 47:2 (2007) 139-158</enrichment>
    <author>Frank van den Eijkhof</author>
    <author>Hans L. Bodlaender</author>
    <author>Arie M.C.A. Koster</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-49</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>weighted treewidth</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>preprocessing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>probabilistic networks</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="05C85">Graph algorithms [See also 68R10, 68W05]</collection>
    <collection role="msc" number="68R10">Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]</collection>
    <collection role="msc" number="68T37">Reasoning under uncertainty</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="NWO-TACO">NWO-TACO</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/716/ZR-02-49.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/716/ZR-02-49.pdf</file>
  </doc>
  <doc>
    <id>665</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2001-12-14</completedDate>
    <publishedDate>2001-12-14</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Pre-processing for Triangulation of Probabilistic Networks</title>
    <abstract language="eng">The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.</abstract>
    <identifier type="serial">01-39</identifier>
    <identifier type="opus3-id">666</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6655</identifier>
    <enrichment key="SourceTitle">An extended vers. appeared in: Computational Intelligence 21:3 (2005) 286-305. Appeared in: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, J. Breese and D. Koller Eds., (2001), pp. 32-39, Published by Morgan Kaufmann Publishers, San Francisco</enrichment>
    <author>Hans L. Bodlaender</author>
    <author>Arie M.C.A. Koster</author>
    <author>Frank van den Eijkhof</author>
    <author>Linda C. van der Gaag</author>
    <series>
      <title>ZIB-Report</title>
      <number>01-39</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>triangulation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>treewidth</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>probabilistic networks</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>pre-processing</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="05C85">Graph algorithms [See also 68R10, 68W05]</collection>
    <collection role="msc" number="68R10">Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]</collection>
    <collection role="msc" number="68T37">Reasoning under uncertainty</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/665/ZR-01-39.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/665/ZR-01-39.pdf</file>
  </doc>
</export-example>
