Dynamic programming on Nice Tree Decompositions

Abstract

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.