At the beginning of the 1970s, it was observed that a large class of combinatorial optimization problems defined on graphs could be efficiently solved by non serial dynamic programming as long as the graph had a bounded dimension, a parameter shown to be equivalent to treewidth by .
As an example, the problem of coloring graph of treewidth k may be solved by using a dynamic programming algorithm on a tree decomposition of the graph.