G. Charwat:

"Dynamic Programming on Tree Decompositions using Binary Decision Diagrams";

Talk: 31st International Conference on Logic Programming, ICLP-DC 2015, Cork, Irland; 08-31-2015 - 09-04-2015; in: "Proceedings of the Technical Communications of the 31st International Conference on Logic Programming (ICLP 2015), Cork, Ireland, August 31 - September 4, 2015", M. De Vos, T. Eiter, Y. Lierler, F. Toni (ed.); CEUR-WS.org, Volume 1443 (2015), 10 pages.

Dynamic programming (DP) on tree decompositions is a well studied approach for solving hard problems encodingsciently. State-of-the-art implementations usually rely on tables for storing information, and algorithms specify how the tuples are manipulated during traversal of the decomposition. However, a major bottleneck of such table-based algorithms is relatively high memory consumption. The goal of the doctoral thesis herein discussed is to mitigate performance and memory shortcomings of such algorithms. The idea is to replace tables with an encodingscient data structure that no longer requires to enumerate intermediate results explicitly during the computation. To this end, Binary Decision Diagrams (BDDs) and related concepts are studied with respect to their applicability in this setting. Besides native support for encodingscient storage, from a conceptual point of view BDDs give rise to an alternative approach of how DP algorithms are specified. Instead of tuple-based manipulation operations, the algorithms are specified on a logical level, where sets of models can be conjointly updated. The goal of the thesis is to provide a general tool-set for problems that can be solved efficiently via DP on tree decompositions.

Project Head Stefan Woltran:

START

Created from the Publication Database of the Vienna University of Technology.