Hi, how are you? I'm the guy who started the tread about tree decomposition. I implemented a non optimistic algorithm which return a tree with (|V|- 1 ) nodes with a tree width (|V|- 1 ).
I think I have misunderstood one part of the algorithm and it's probably the return statement (the one when n is not 1).
Thread with more info : http://math.stackexchange.com/questions/1246421/tree-decomposition-by-hand-for-understanding
I think I have misunderstood one part of the algorithm and it's probably the return statement (the one when n is not 1).
Thread with more info : http://math.stackexchange.com/questions/1246421/tree-decomposition-by-hand-for-understanding
I'm looking for a fast in practice algorithm for calculating the (preferable optimized) tree decomposition of a graph.
I found the paper "A linear time algorithm for finding tree-decompositions of small treewidth" [1] by Hans L. Bodlaender which return a tree-decompsiton with the optimized tre...
Do you know sensible algorithms that run in polynomial time in (Input length + Output length), but whose asymptotic running time in the same measure has a really huge exponent/constant (at least, where the proven upper bound on the running time is in such a way)?
There are some nonconstructive algorithms, most notably Fellows and Langston and Courcelle's theorem.
Also, Bodlaender's linear-time algorithm for tree-width and Courcelle's theorem are notoriously impractical.
