Dynamic programming on Nice Tree Decompositions
Institution: | Universiteit Utrecht |
---|---|
Department: | |
Year: | 2015 |
Keywords: | treewidth,Steiner tree problem,dynamic programming |
Record ID: | 1247407 |
Full text PDF: | http://dspace.library.uu.nl:8080/handle/1874/309652 |
Connectivity problems such as the Steiner Tree Problem are NP-hard problems that are fixed parameter tractable in the treewidth of the input graph. In this thesis a dynamic programming algorithm on nice tree decompositions is discussed. Based on observations on nice tree decomposition diversity and experiment results, a number of optimization heuristics are proposed to speed up computation. By restructuring the nice tree decomposition, all tested input graphs show a considerable improvement both in amount of processed partial solutions as well as computation time. Furthermore a number of different data structures are analyzed, that allow for various constant time operations for graphs of low treewidth.