[Back]


Talks and Poster Presentations (with Proceedings-Entry):

G. Charwat, S. Woltran:
"Efficient Problem Solving on Tree Decompositions using Binary Decision Diagrams";
Talk: 13th International Conference on Logic Programming and Non-monotonic Reasoning, LPNMR 2015, Lexington, Kentucky, USA; 09-27-2015 - 09-30-2015; in: "Logic Programming and Nonmonotonic Reasoning, 13th International Conference, LPNMR 2015, Lexington, KY, USA, September 27-30, 2015, Proceedings", F. Calimeri, G. Ianni, M. Truszczynski (ed.); Springer, Lecture Notes in Computer Science Volume 9345 (2015), ISBN: 978-3-319-23263-8; 213 - 227.



English abstract:
Dynamic programming (DP) on tree decompositions is a well studied approach for solving hard problems efficiently. Usually, implementations rely on tables for storing information, and algorithms specify how tuples are manipulated during traversal of the decomposition. However, a bottleneck of such table-based algorithms is relatively high memory consumption. Binary Decision Diagrams (BDDs) and related concepts have been shown to be very well suited to store information efficiently. While several techniques have been proposed that combine DP with efficient BDD-based storage for some particular problems, in this work we present a general approach where DP algorithms are specified on a logical level in form of set-based formula manipulation operations that are executed directly on the BDD data structure. In the paper, we provide several case studies in order to illustrate the method at work, and report on preliminary experiments. These show promising results, both with respect to memory and run-time.


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-319-23264-5_19



Related Projects:
Project Head Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen

Project Head Stefan Woltran:
START


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