Skip to Content

TU Wien Fakultät für Informatik DBAI Database and Artificial Intelligence Group
Top-level Navigation: Current-level Navigation:

Path: DBAI > Research > Projects > Decodyn > dynBDD

Tools: Print

dynBDD: Dynamic Programming on Tree Decompositions using Binary Decision Diagrams

About

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.

The software tool dynBDD comprises a collection of prototypical implementations of DP algorithms. The algorithms are specified on a logical level in form of set-based formula manipulation operations which are executed directly on the underlying BDD data structure.

Problems

dynBDD v0.1-beta can solve the following problems: 3-Colorability, Hamiltonian Cycle, Stable Extensions, Boolean Satisfiability. It supports different normalization types of tree decompositions: none, weak-/semi-/normalized. Each algorithm is implemented in two variants: early and late decision method.

Downloads

Releases:

Test Instances: