<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>820</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2004-11-08</completedDate>
    <publishedDate>2004-11-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the Maximum Cardinality Search Lower Bound for Treewidth</title>
    <abstract language="eng">The Maximum Cardinality Search algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbors becomes visited. An MCS-ordering of a graph is an ordering of the vertices that can be generated by the Maximum Cardinality Search algorithm. The visited degree of a vertex $v$ in an MCS-ordering is the number of neighbors of $v$ that are before $v$ in the ordering. The visited degree of an MCS-ordering $\psi$ of $G$ is the maximum visited degree over all vertices $v$ in $\psi$. The maximum visited degree over all MCS-orderings of graph $G$ is called its {\em maximum visited degree}. Lucena (2003) showed that the treewidth of a graph $G$ is at least its maximum visited degree. We show that the maximum visited degree is of size $O(\log n)$ for planar graphs, and give examples of planar graphs $G$ with maximum visited degree $k$ with $O(k!)$ vertices, for all $k\in \Bbb{N}$. Given a graph $G$, it is NP-complete to determine if its maximum visited degree is at least $k$, for any fixed $k\geq 7$. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete. We also propose and experimentally analyses some heuristics for the problem. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.</abstract>
    <identifier type="serial">04-45</identifier>
    <identifier type="opus3-id">821</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8201</identifier>
    <enrichment key="SourceTitle">Appeared in: Discrete Applied Mathematics 155 (2007) 1348-1372. An extended abstract appeared in: Proceedings of International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004, Lecture Notes in Computer Science 3353, 2005, 81-92</enrichment>
    <author>Hans L. Bodlaender</author>
    <author>Arie M.C.A. Koster</author>
    <series>
      <title>ZIB-Report</title>
      <number>04-45</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>maximum cardinality search</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>treewidth</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>lower bounds</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>planar graphs</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>graph algorithms</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="68Q25">Analysis of algorithms and problem complexity [See also 68W40]</collection>
    <collection role="msc" number="68R10">Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]</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/820/ZR-04-45.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/820/ZR-04-45.pdf</file>
  </doc>
  <doc>
    <id>887</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2005-12-13</completedDate>
    <publishedDate>2005-12-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Treewidth Lower Bounds with Brambles</title>
    <abstract language="eng">In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph $G$ is the maximum order of a bramble of $G$ minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms give often excellent lower bounds, in particular when applied to (close to) planar graphs.</abstract>
    <identifier type="serial">05-54</identifier>
    <identifier type="opus3-id">887</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8878</identifier>
    <enrichment key="SourceTitle">Appeared in: Algorithmica 51 (2008) 81-98. An extended abstract appeared in: Proc. 13th Ann. Europ. Symp. on Algorithms, ESA 2005, LNCS 3669, Springer 2005, pp. 391-402</enrichment>
    <author>Hans L. Bodlaender</author>
    <author>Alexander Grigoriev</author>
    <author>Arie M.C.A. Koster</author>
    <series>
      <title>ZIB-Report</title>
      <number>05-54</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>treewidth</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>lower bounds</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branchwidth</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>brambles</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="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="NWO-TACO">NWO-TACO</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/887/ZR-05-54.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/887/ZR-05-54.ps</file>
  </doc>
  <doc>
    <id>754</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2003-09-29</completedDate>
    <publishedDate>2003-09-29</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Safe separators for treewidth</title>
    <abstract language="eng">A set of vertices $S\subseteq V$ is called a safe separator for treewidth, if $S$ is a separator of $G$, and the treewidth of $G$ equals the maximum of the treewidth over all connected components $W$ of $G-S$ of the graph, obtained by making $S$ a clique in the subgraph of $G$, induced by $W\cup S$. We show that such safe separators are a very powerful tool for preprocessing graphs when we want to compute their treewidth. We give several sufficient conditions for separators to be safe, allowing such separators, if existing, to be found in polynomial time. In particular, every minimal separator of size one or two is safe, every minimal separator of size three that does not split off a component with only one vertex is safe, and every minimal separator that is an almost clique is safe; an almost clique is a set of vertices $W$ such that there is a $v\in W$ with $W-\{v\}$ a clique. We report on experiments that show significant reductions of instance sizes for graphs from proba! bilistic networks and frequency assignment.</abstract>
    <identifier type="serial">03-32</identifier>
    <identifier type="opus3-id">755</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7544</identifier>
    <enrichment key="SourceTitle">Appeared in: Discrete Mathematics 306:3 (2006) 337-350. An extended abstract appeared in: Joint Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX '04) and the Workshop on Analytic Algorithmics and Combinatorics (ANALCO '04), New Oreleans, SIAM Proceedings, pp. 70-78 (2004)</enrichment>
    <author>Hans L. Bodlaender</author>
    <author>Arie M.C.A. Koster</author>
    <series>
      <title>ZIB-Report</title>
      <number>03-32</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>treewidth</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>safe separators</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>preprocessing</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="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="NWO-TACO">NWO-TACO</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/754/ZR-03-32.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/754/ZR-03-32.pdf</file>
  </doc>
  <doc>
    <id>804</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2004-07-28</completedDate>
    <publishedDate>2004-07-28</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Contraction and Treewidth Lower Bounds</title>
    <abstract language="eng">Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the minimum degree. The degeneracy is polynomial time computable. We introduce the notion of contraction degeneracy: the maximum over all minors of the minimum degree. We show that the contraction degeneracy problem is NP-complete, even for bipartite graphs, but for fixed $k$, it is polynomial time decidable if a given graph $G$ has contraction degeneracy at least $k$. Heuristics for computing the contraction degeneracy are proposed and evaluated. It is shown that these can lead in practice to considerable improvements of the lower bound for treewidth, but can perform arbitrarily bad on some examples. A study is also made for the combination of contraction with Lucena's lower bound based on Maximum Cardinality Search (Lucena, 2003). Finally, heuristics for the treewidth are proposed and! evaluated that combine contraction with a treewidth lower bound technique by Clautiaux et al (2003).</abstract>
    <identifier type="serial">04-29</identifier>
    <identifier type="opus3-id">805</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8042</identifier>
    <enrichment key="SourceTitle">Appeared in: Journal of Graph Algorithms and Applications 10:1 (2006) 5-49. An extended abstract appeared in: Proceedings of 12th Annual European Symposium on Algorithms (ESA), Bergen, Norway, 628-639 (2004)</enrichment>
    <author>Hans L. Bodlaender</author>
    <author>Arie M.C.A. Koster</author>
    <author>Thomas Wolle</author>
    <series>
      <title>ZIB-Report</title>
      <number>04-29</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>treewidth</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>contraction degeneracy</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>graph minors</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>lower bounds</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>maximum cardinality search</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="05C83">Graph minors</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="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="NWO-TACO">NWO-TACO</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/804/ZR-04-29.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/804/ZR-04-29.pdf</file>
  </doc>
  <doc>
    <id>664</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-11</completedDate>
    <publishedDate>2001-12-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Treewidth: Computational Experiments</title>
    <abstract language="eng">Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse optimization problems. To apply a tree decomposition approach, the treewidth of the graph has to be determined, independently of the application at hand. Although for fixed $k$, linear time algorithms exist to solve the decision problem ``treewidth $\leq k$'', their practical use is very limited. The computational tractability of treewidth has been rarely studied so far. In this paper, we compare four heuristics and two lower bounds for instances from applications such as the frequency assignment problem and the vertex coloring problem. Three of the heuristics are based on well-known algorithms to recognize triangulated graphs. The fourth heuristic recursively improves a tree decomposition by the computation of minimal separating vertex sets in subgraphs. Lower bounds can be computed from maximal cliques and the minimum degree of induced subgraphs. A computational analysis shows that the treewidth of several graphs can be identified by these methods. For other graphs, however, more sophisticated techniques are necessary.</abstract>
    <identifier type="serial">01-38</identifier>
    <identifier type="opus3-id">665</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6644</identifier>
    <enrichment key="SourceTitle">An extended abstract appeared in: Electronic Notes in Discrete Mathematics. H. Broersma, U. Faigle, J. Hurink, S. Pickl (eds.), vol. 8. Elsevier Publ. 2001.</enrichment>
    <author>Arie M.C.A. Koster</author>
    <author>Hans L. Bodlaender</author>
    <author>Stan P.M. van Hoesel</author>
    <series>
      <title>ZIB-Report</title>
      <number>01-38</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>treewidth</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>heuristics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>lower bounds</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>computations</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="90C35">Programming involving graphs or networks [See also 90C27]</collection>
    <collection role="msc" number="94C15">Applications of graph theory [See also 05Cxx, 68R10]</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/664/ZR-01-38.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/664/ZR-01-38.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>
  <doc>
    <id>926</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2006-06-16</completedDate>
    <publishedDate>2006-06-16</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On exact algorithms for treewidth</title>
    <abstract language="eng">We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time $O^\ast(2^n)$. This algorithm is based on the old dynamic programming method introduced by Held and Karp for the {\sc Tra veling Salesman} problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. However, our experiments show that the space use d by the algorithm is an important factor to what input sizes the algorithm is effective. For this purpose, we settle the problem of computing treewidth under the restriction that the space used is only polynomial. In this direction we give a simple $O^\ast(4^n)$ al gorithm that requires {\em polynomial} space. We also show that with a more complicated algorithm, using balanced separators, {\sc Treewidth} can be computed in $O^\ast(2.9512^n)$ time and polynomial space.</abstract>
    <identifier type="serial">06-32</identifier>
    <identifier type="opus3-id">926</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9265</identifier>
    <enrichment key="SourceTitle">An extended abstract appeared in: Proceedings 14th Annual European Symposium on Algorithms, ESA 2006, Lecture Notes in Computer Science, Vol. 4168, 2006, pp. 672-683</enrichment>
    <author>Hans L. Bodlaender</author>
    <author>Fedor V. Fomin</author>
    <author>Arie M.C.A. Koster</author>
    <author>Dieter Kratsch</author>
    <author>Dimitrios M. Thilikos</author>
    <series>
      <title>ZIB-Report</title>
      <number>06-32</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>treewidth</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>exponential algorithms</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="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="NWO-TACO">NWO-TACO</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/926/ZR-06-32.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/926/ZR-06-32.ps</file>
  </doc>
</export-example>
