Treewidth
of Graphs
Motivated by the success of the dynamic programming algorithm for frequency assignment based on a tree-decomposition of the constraint graph, we started a resaerch project on finding good tree decompositions in a graph. The idea is that with good methods to compute the treewidth of graphs, the tree-decomposition approach to solve combinatorial optimization problems will become commonly accepted as an alternative for integer programming techniques.
The concept of treewidth is related with finding a triangulation of a graph with minimum clique number. This relation led to joint research with people from the field of probabilistic networks where these triangulations play an important role as well.