There are many graph problems that can be solved in linear or polynomial time with a
dynamic programming algorithm when the input graph has bounded treewidth. For …

LNCS 4474 - Treewidth: Structure and Algorithms Page 1 Treewidth: Structure and Algorithms
Hans L. Bodlaender Institute of Information and Computing Sciences, Utrecht University, PO …

Any given graph can be embedded in a chordal graph by adding edges, and the resulting
chordal graph is called a triangulation of the input graph. In this paper we study minimal …

Treewidth is a graph parameter with several interesting theoretical and practical
applications. This survey reviews algorithmic results on determining the treewidth of a given …

This paper gives a short survey on algorithmic aspects of the treewidth of graphs. Some
alternative characterizations and some applications of the notion are given. The paper also …

For more than 30 years Davis-Putnam-style exponentialtime backtracking algorithms have
been the most common tools used for finding exact solutions of NP-hard problems. Despite …

We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O
(1.7159 n). This result can be seen as an algorithmic proof of the fact that the number of …

Davis-Putnam-style exponential-time backtracking algorithms are the most common
algorithms used for finding exact solutions of NP-hard problems. The analysis of such …

This paper presents algorithms whose input is an undirected graph, and whose output is a
tree decomposition of width that approximates the optimal, the treewidth of that graph. The …

We show that the treewidth and the minimum fill-in of an n-vertex graph can be computed in
time O(1.8899^n). Our results are based on combinatorial proofs that an n-vertex graph has …