AAAI Publications, Workshops at the Thirtieth AAAI Conference on Artificial Intelligence

Font Size: 
Subset Minimization in Dynamic Programming on Tree Decompositions
Bernhard Bliem, Günther Charwat, Markus Hecher, Stefan Woltran

Last modified: 2016-03-29


Many problems from the area of AI have been shown tractable for bounded treewidth. In order to put such results into practice, quite involved dynamic programming (DP) algorithms on tree decompositions have to be designed and implemented. These algorithms typically show recurring patterns that call for tasks like subset minimization. In this paper, we provide a new method for obtaining DP algorithms from simpler principles, where the necessary data structures and algorithms for subset minimization are automatically generated. Moreover, we discuss how this method can be implemented in systems that perform more space-efficiently than current approaches.

Full Text: PDF