Algorithms on Tree Decompositions and Time Improvements
Hans L. Bodlaender
Institute of Information and Computing Sciences, Utrecht University, The Netherlands
Institute of Information and Computing Sciences, Utrecht University, The Netherlands
2011/10/31 Mon 4PM-5PM
Many problems that are intractable on general graphs become linear time solvable on graphs of bounded treewidth. The constant factor however of such algorithms is exponential or worse in the treewidth of the tree decomposition that is used. In this talk, a number of known and some new results are surveyed. In particular, it is shown how speed improvements can be obtained using convolutions, and how a recent technique called “cut-and-count” can be used to obtain fast probabilistic algorithms for problems like Hamiltonian Circuit.