Talk:Tree decomposition

From Wikipedia, the free encyclopedia

What's the relation between this and Junction tree or join tree? Are they the same? Took 03:13, 20 March 2007 (UTC)

I think they are the same, and merged them. There was a very vague handwavy description of how to find a tree decomposition in the junction tree article, which I didn't consider worth saving, but there's plenty more that could be said in this article on the topic of decomposition algorithms. This should link in to graph separators, as well. —David Eppstein 16:30, 3 November 2007 (UTC)

[edit] The recursion for Independent Set

I have a suggestion for a different formulation of A in the recursion for Independent Set. Let C(i) be the direct children of node i in the tree decomposition. (Since we have chosen a root for the tree this is ok.)

A(S,i)= |S| + \sum_{j \in C(i)} \left( ( \max_{ S'\subset X_j \atop { S\cap X_j = S' \cap X_i \atop S \cup S' \text{independent set}} } A(S',j) ) - |S\cap X_j| \right)

This way we dont need the extra function B. What do you think? Dag Hovland (talk) 10:37, 7 December 2007 (UTC)


[edit] Books?

Could anyone provide a reference for a really good book covering this and similar (algorithms and graph theory) topics? —Preceding unsigned comment added by 81.110.32.149 (talk) 19:42, 8 January 2008 (UTC)