I am implementing "algorithm 2" from the paper "Treewidth computations I. Upper bounds" by Bodlander and Koster[1,page5] and I am not sure if I understand it or not.
As I understand, the algoritm will always return a tree decomposion that looks like a linked list.
If there are n nodes in the tree, then the tree will have n-1 edges. Is that correct?
I tried the algorithm by hand: http://oi59.tinypic.com/nz4y1d.jpg
I have three lines in each column. The first column is the input graph, the second is the graph after I have eliminated v1, and the last line in red are the tree decomposition. I start from the left and I go to the right column for each recursive call.
Have I understood it correctly
[1] http://www.math2.rwth-aachen.de/~koster/paper/boko08b_rv.pdf
Edit: I think I have problem to understand the return statement when n =/= 1