  In this paper, we present a Branch and Bound algorithm called QuickBB for
computing the treewidth of an undirected graph. This algorithm performs a
search in the space of perfect elimination ordering of vertices of the graph.
The algorithm uses novel pruning and propagation techniques which are derived
from the theory of graph minors and graph isomorphism. We present a new
algorithm called minor-min-width for computing a lower bound on treewidth that
is used within the branch and bound algorithm and which improves over earlier
available lower bounds. Empirical evaluation of QuickBB on randomly generated
graphs and benchmarks in Graph Coloring and Bayesian Networks shows that it is
consistently better than complete algorithms like QuickTree [Shoikhet and
Geiger, 1997] in terms of cpu time. QuickBB also has good anytime performance,
being able to generate a better upper bound on treewidth of some graphs whose
optimal treewidth could not be computed up to now.
