A Complete Anytime Algorithm for Treewidth

Understand

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.