Space-efficient construction variants of dynamic programming
Hans L. Bodlaender, Jan Arne Telle · 2004
Many dynamic programming algorithms that solve a decision problem can be modified to one that solves the construction variant of the problem by additional bookkeeping and going backwards through stored answers to subproblems. It is also well known that for many dynamic programming algorithms, one can save memory space by throwing away tables of information that is no longer needed, thus reusing the memory. Somewhat surprisingly, the observation that these two modifications cannot be combined is frequently not made. In this paper we consider the case of dynamic programming algorithms on graphs of bounded treewidth. We give algorithms to solve the construction variants of such problems that use only twice the amount of memory space of the decision versions, with only a logarithmic factor increase in running time. Using the concept of strong directed treewidth we then discuss how these algorithms can be applied to dynamic programming in general.